Fusion Via a Linear Combination of Scores.
We present a thorough analysis of the capabilities of the linear combination (LC) model for fusion of information retrieval systems. The LC model combines the results lists of multiple IR systems by scoring each document using a weighted sum of the scores from each of the component systems. We first present both empirical and analytical justification for the hypotheses that such a model should only be used when the systems involved have high performance, a large overlap of relevant documents, and a small overlap of nonrelevant documents. The empirical approach allows us to very accurately predict the performance of a combined system. We also derive a formula for a theoretically optimal weighting scheme for combining 2 systems. We introduce dthe difference between the average score on relevant documents and the average score on nonrelevant documentsas a performance measure which not only allows mathematical reasoning about system performance, but also allows the selection of weights which generalize well to new documents. We describe a number of experiments involving large numbers of different IR systems which support these findings.
Introduction
In the past, neural network models which have been
applied to the Information Retrieval problem have typ-
Research was supported by UC Senate Bridge Grant #RW252G/B.
ically used the very large feature vectors (document and
query vectors) which are traditionally used in IR systems
(see for example, [Crestani, 1994], [Wong et al.,
1993], [Boughanem et al., 1993]). Unfortunately, the
2 Vogt and Cottrell
resulting large networks generally require large numbers
of training examples, a rare commodity in the IR
setting. Although work using Latent Semantic Indexing
[Deerwester et al., 1990] to reduce the number of
features has met with some success [Vogt et al., 1997a],
LSI is itself computationally expensive.
Perhaps a wiser approach can be found in fusion,
where the results from multiple IR systems are combined
to generate a single (hopefully better) list of
potentially relevant documents in response to presentation
of a single query to a number of component
systems. Fusion allows a significant reduction in the
number of features, often to just one feature per system
- typically the system's estimate of the document's
probability of relevance. As such, a fusion neural net-work
model can be much smaller than a traditional
one based on document vectors. Fusion also allows
leveraging of the component systems in several ways
by exploiting a number of effects (from [Diamond,
ffl The Skimming Effect happens when "retrieval
approaches that represent their collection items
differently retrieve different relevant items, so that
a combination method that takes the top-ranked
items from each of the retrieval approaches will
push non-relevant items down in the ranking."
ffl The Chorus Effect occurs "when several retrieval
approaches suggest that an item is relevant to a
query.this tends to be stronger evidence for relevance
than a single approach doing so."
ffl The Dark Horse Effect in which "a retrieval approach
may produce unusually accurate (or inac-
curate) estimates of relevance for at least some
items, relative to the other retrieval approaches."
It should be noted that when choosing how to combine
the results from different IR systems, the Dark Horse
Effect is at odds with the Chorus Effect. Likewise, a
large Chorus Effect cuts into the possible gain from
the Skimming Effect. These phenomena argue for a
sophisticated fusion model which is able to predict
when these effects will occur and take advantage of
them. Furthermore, the expansion of the Word Wide
Web has spawned a proliferation of search engines.
Combining them would allow one to exploit the above
effects.
Such simple neural network fusion models may allow
easier training, but their simplicity inflicts a penalty
- they lack expressive power. Thus, it seems likely that
the improvement in performance possible from these
models would be limited. In this article, we examine in
detail one such fusion model: the linear combination
of scores (LC). The LC model has been used by many
researchers with varying degrees of success [Bartell
et al., 1994], [Kantor, 1995], [Knaus et al., 1995], [Sel-
berg and Etzioni, 1996], [Shaw and Fox, 1995], and
Fusion Via a Linear Combination of Scores 3
[Vogt et al., 1997b]. Our analysis of the model reveals
what types of systems the model works best with and
explores techniques for training the model.
This article has the following format. First we describe
the model and the specific problems we are ex-
amining, along with the data we use and assumptions.
Next, we both empirically and mathematically derive
explanations for when it makes sense to use the LC
model. This also leads to hard limits on the performance
of an LC fusion system. Finally, we describe
experiments in training the LC model, and describe a
technique which generalizes to large numbers of systems
as well as more complicated models. Through
these analyses we gain insight into why and when the
LC model works well.
2. Background
2.1. The LC Model
The linear combination model calculates the real-valued
relevance ae of a document x to a query q based
on the weights given to each individual
system and their estimates of relevance:
ae(w;
systems
This value is then used to rank the documents. For
only two IR systems, this simplifies to:
However, all that really matters is the ranking given
by the combined system. Thus, for the case of two
systems, only the ratio of the two weights and the
relationship of the signs on the weights are important,
and equation (1) can be replaced by one using a single
weight:
ae(w;
The LC model is more flexible than others which
have been tried in the past. Most of these consist of a
single choice of parameters, such as the sum of scores
or the maximum score, or a fixed weighting based
on individual system performance (see [Belkin et al.,
1995], [Shaw and Fox, 1995], [Kantor, 1995]). The
difference here is that we will use a search procedure to
optimize the weights. The LC model is also equivalent
to the simplest kind of neural network, a single layer
net. The addition of a squashing function on the output
unit does not add any power, as it would not change
the ranking induced by the combined system.
2.2. The Data
Our study of fusion necessitates the availability of a
large number of IR systems. We have chosen to use
the entries to the TREC5 adhoc track [Harman, 1997].
TREC (Text REtrieval Conference) is an annual conference
sponsored by the National Institute of Standards
and Technology, in which participants are given
very large text corpora and submit the results of their
4 Vogt and Cottrell
retrieval techniques in a sort of contest. Specifically,
in the adhoc track, each participant submits the top
1000 documents returned by their system in response
to 50 queries supplied by NIST, and each participant
can submit up to 4 runs. 61 runs were submitted, for
a total of 3050 lists of 1000 documents, each of which
we treat as a separate IR "system." Although most of
our work involves examining the routing problem, we
choose the adhoc entries because there are far more of
them than routing entries.
One issue arises when combining such lists of top-ranked
documents - what score should be given to
documents returned by one system but not the other?
We have assumed that for such documents, the system
which did not return them gave them a score of zero. In
so doing, we also had to eliminate any negative scores
for documents, because otherwise the unreturned documents
would get ranked above those with negative
scores. We did this by adding the absolute value of the
lowest score to all documents for any system which had
negative scores. We believe that zero scores for unseen
documents is a reasonable choice - the vast majority
of documents are not relevant, and most systems give
a zero score to nonrelevant documents.
2.3. Problems Addressed
A common dichotomy used by fusion researchers is
the difference between data fusion and collection fu-
sion. The former takes place in a setting when all
of the IR systems involved have access to the same
text collection. The latter is used when the collections
searched by all IR systems are disjoint. Because of our
use of TREC entries, our work necessarily falls under
the label of data fusion, but it is not data fusion in the
purest sense, since we do not have scores for all of the
documents in the corpus.
Another distinction is in the type of IR problem
solved. TREC distinguishes two main problems: ad-hoc
and routing. Adhoc retrieval occurs when the text
collection is relatively static, and new queries are constantly
being submitted by users. In contrast, routing
has a standing query, and new documents are arriving
which need to be filtered according to that query.
The difference between these two tasks is important
in the context of the LC model. For the routing task,
a new set of weights can be trained for each standing
query. However, for the adhoc task, one set of weights
must be applied for all queries. Clearly, the routing
task should be easier to solve using this model, since
the weights can be tuned on a per-query basis.
3. Limitations of the LC Model
Using the LC model does not always result in an improvement
in performance. Previous work using the
TREC data has shown that even on the training set, significant
improvement is achievable for less than half of
the possible combinations [Vogt and Cottrell, 1998a].
Fusion Via a Linear Combination of Scores 5
Why is it that it works sometimes and not others?
When does the LC model work?
In this section we use two techniques, one empirical
and one analytical, to determine the source of the LC
model's power. In the process, we gain a deeper understanding
of why it works, its limitations, and which
systems can be successfully combined using the LC
model.
3.1. Empirical Analysis
We introduce here a technique for analyzing the behavior
of fusion models and applied it to the LC model.
The technique involves measuring various properties of
the component IR systems, and using them in a linear
regression to predict the performance of the combination
[Vogt and Cottrell, 1998a]. By examining how
the measures are weighted by the regression, we gain
an intuitive feel for when using the model pays off.
Our technique works surprisingly well - the resulting
regression can predict the performance of unseen combinations
very accurately (on the test set, r
3.1.1. Method Our data set is all 61 TREC5 entries
on the first 20 queries - 1220 lists of up to 1000 docu-
ments. We begin by making a number of measures of
all 36,600 pairs of systems/queries. These measures
are meant to indicate either how well each system performs
or how similar the two systems are to each other.
The performance measures include average precision
(indicated by P) and a statistical measure of rank correlation
between the system and the relevance judgments
(J) [Bartell et al., 1994]. J is defined as:
ae(w;
indicates the user prefers document x to
document x 0 on query q. Note that J has a maximum
value of 1 when the numerator and denominator are the
same (i.e., the IR system ranks documents exactly as
the user would), and a minimum value of -1 when the
opposite is true. These two measures are subscripted
a for the better of the two systems and b for the worse.
The pairwise similarity measures include:
ffl Guttman's Point Alienation (GPA) - a measure
of how similar two rankings are to each other and
which is calculated as:
ffl the number of documents in the intersection of the
two lists of returned documents (")
ffl the correlation coefficient from a linear regression
of the scores of documents in the intersection of
the two systems (C)
ffl the number of relevant documents returned by one
system but not the other divided by the total num-
6 Vogt and Cottrell
ber of relevant documents returned by that system
(U for uniqueness),
ffl Lee's [Lee, 1997] overlap measures, O rel and
O nonrel , which measure the proportion of relevant
and nonrelevant documents in the intersection of
the two lists. These two measures are calculated
as:
O
O
where R i is the number of relevant documents
returned by system i, and N i is the number of
nonrelevant.
Also, because it seemed likely that measuring the similarity
of the two systems on nonrelevant documents
is less important than on relevant ones, the first three
measures were also calculated using only relevant doc-
uments, and are denoted: GPA rel rel . One
last measure, GPA ni (for "not irrelevant") is the GPA
using pairs of documents where at least one is relevant.
After normalizing the scores for each system on each
query by dividing by their respective means we found
the optimal combination for each possible pair. For
each query and each pair of systems, the single weight
w was chosen by optimizing average precision using
golden section search [Press et al., 1995], and the best
w was used to generate a combined system (of 1000
documents) according to equation (2). Because systems
were combined on a per-query basis, this experimental
setup most accurately simulated the routing
task.
We then performed a multiple linear regression using
the aforementioned measures as predictor variables and
the average precision of the optimal combination as the
target. 80% of the pairs (29,280 total - the "training
were used in the regression.
3.1.2. Results Table 1 presents the results of the
multiple regression. Measures are sorted by decreasing
F value, indicating roughly how important each
measure is in predicting the average precision of the
optimally combined system. All measures above the
horizontal line in the table contribute to some degree
(as indicated by F values much larger than 1). The
indicates that the fit of the model is
very accurate. Furthermore, the model generalizes extremely
well to new data - when the remaining 20% of
the pairs (the "test set") were plugged into the model,
Positive regression coefficients in Table 1 can be interpreted
as meaning that the correponding measures
should be maximized in order to maximize the performance
of the combined system. Likewise, measures
with negative coefficients should be minimized. This
leads to the following conclusions: the better system
should have high performance (P a and J a have large
positive coefficients), whereas the performance of the
Fusion Via a Linear Combination of Scores 7

Table

1. Results of Linear Regression
Normalized
Regression
Measure Coefficient F
Pa 0.8993 129141.5501
Ua -0.1202 405.5097
Ja 0.0431 346.1357
GPA rel -0.0359 220.1937
O rel -0.0519 55.8835
C rel 0.0125 35.8910
O nonrel -0.0427 20.9289
" rel 0.0088 17.5199
GPA ni -0.0099 8.9850
Results of a linear regression for predicting the combination's average
precision (r 2 =0.94). Positive coefficients indicate the measure
should be maximized, negative coefficients indicate it should be
minimized.
worse system may or may not be good (Pb and Jb have
opposite signs). The positive coefficients on GPA and
C rel indicate that the two systems should generally
rank documents in their intersection similarly and the
distribution of scores by both systems should be similar
to each other. On the other hand, the negative
coefficients on GPA rel and GPA ni indicate that each
system should rank relevant documents differently than
the other system. Finally, the negative coefficient on
O nonrel means that the two systems should retrieve
different sets of nonrelevant documents.
The table leads to conflicting conclusions about the
overlap of relevant documents. The negative coefficients
for U a and U b indicate that both systems should
not return unique relevant documents, whereas the negative
coefficient on O rel indicates they should. As it
turns out, the negative coefficient on O rel is inaccurate
because O rel is directly related to U a and U b by2O rel
. The regression simply accounted
for the effect of uniqueness using U a and U b
alone.
In fact, by repeating the regression using only
O rel and O nonrel , we can predict the combined
system's precision with nearly the same accuracy
as the original regression (r
2). This table shows that the following three conclusions
about when it makes sense to use the LC model
are strongest, namely when:
ffl at least one exhibits good performance,
ffl both return similar sets of relevant documents, and
ffl both return dissimilar sets of nonrelevant documents

8 Vogt and Cottrell

Table

2. Results of Linear Regression on a Subset of Predictors
Normalized
Regression
Measure Coefficient F
Pa 0.9366 191543.1029
O rel 0.1021 2249.4031
O nonrel -0.0581 975.4101
3.2. Mathematical Analysis
The conclusions in the previous section were arrived at
empirically, and give little insight into why they may
be true. We now provide a mathematical justification
for these hypotheses. Furthermore, we mathematically
derive an equation for the optimal weighting and
from this derivation arrive at an equation for the performance
of an LC model. As in the empirical case,
we concentrate on the routing problem only.
3.2.1. d as a Performance Measure Our analysis
hinges on the use of d as a performance measure. d
is equal to the difference between the mean score on
all positive examples (relevant documents) -
p and the
mean score on all negative examples (nonrelevant doc-
As such, d is most easily applied to evaluating
the routing task, where documents need to be
placed in one of two categories. Without loss of gen-
erality, we assume the scores have been normalized
to the interval [0; 1], to make values of d comparable
across systems. d is equal to the numerator of d 0 from
signal detection theory [Swets, 1996]. d 0 divides this
difference by the standard deviation of the negative example
score distribution (d
oe N
A variation of
called the Swets measure has been examined before
in the information retrieval setting ([van Rijsbergen,
1979], p.157):
However, despite their statistically based theoretical
attractiveness and the excellent argument put forth by
Swets, neither d 0 nor S have ever caught on as a basis
for performance evaluation in IR. We now justify our
use of d as a performance measure by relating it to d 0 .
First we note that IR systems typically distribute
scores according to an exponential distribution. Figure
1 shows the empirical distribution of two typical IR
systems from TREC5 after scores have been normalized
to [0; 1]. Note that these distributions are summed
over all 50 queries for each system. Over 60% of the 61
entries have distributions similar to these two. Figure
shows two atypical distributions. The typical distribution
not only has the appearance of an exponential,
but as

Figure

3 shows, it also has the property that its
mean is approximately equal to its standard deviation
- a property of all exponential distributions. Note that
this property is stronger for the negative score distribu-
Fusion Via a Linear Combination of Scores 920060010001400
Relevant Scores - Cor5A1se
Nonrelevant Scores - Cor5A1se20060010001400
Relevant Scores - vtwnB1
Nonrelevant Scores - vtwnB1
Fig. 1. Smoothed Histogram of Typical Relevant and Nonrelevant Score Distributions (from entries Cor5A1se and vtwnB1)
Relevant Scores - INQ301
Nonrelevant Scores - INQ30120060010001400
Relevant Scores - uwgcx0
Nonrelevant Scores - uwgcx0
Fig. 2. Smoothed Histogram of Atypical Relevant and Nonrelevant Score Distributions (from entries INQ301 and uwgcx0)
Fusion Via a Linear Combination of Scores 112610-0.6 -0.4 -0.2 0 0.2 0.4 0.626101418
Fig. 3. Histograms of the difference between the mean and the standard deviation for positive example scores (-p \Gamma oe P , left) and negative
example scores (-n \Gamma oe N , right) on the 61 TREC entries. Note that both are centered around 0 and the negative score histogram has smaller
variance.
tions (the negative score histogram has lower variance),
indicating that it is closer to an exponential.
Because of the aforementioned properties, it is reasonable
to substitute the mean of the negative score
distribution for the standard deviation in the equation
for
We note that maximizing
d is the same as maximizing this approximation to
a measure which has already been well defended
for use in IR [van Rijsbergen, 1979], [Swets, 1996].
To see this, simply take the logarithm of both sides of
the approximation after ignoring the subtraction of a
log(-n).
We further justify the use of d bynoting that on the 61
entries and 50 queries from TREC5, a linear regression
of d to predict average precision yields an r

Figure

4 shows this relationship. Furthermore, as we
will show later, optimizing d has effects similar to
optimizing average precision directly.
3.2.2. An Equation for d Our first step is to derive
an equation for d when combining two systems. We
use the following notation: the letters a and b are
used to indicate the two systems being combined. The
set of relevant documents returned only by system a
are indicated P a (P for positive example), those by
are P b and those returned by both are P ab , with
their sizes shown as P , so that P a = jP a j, etc. The
corresponding sets of nonrelevent documents and their
sizes are indicated using N and N .
We proceed by deriving an expression for - p in terms
of -
p a and -
b , and then likewise for - n. As in our empirical
study, we are trying to predict the performance of
the combined system based on the performance (and
other variables) of the component systems.
ae min be the lowest score produced by the combined
system before normalization, and r be the range
of scores (ae These quantities are used to
12 Vogt and Cottrell
-0.4
d
Average Precision
Fig. 4. Average Precision versus d for the 3050 TREC5 Entries
normalize the scores of the combined system to [0; 1].
Then, by definition,
ab
sin(w) (ae a (x)\Gammaae min )
r
x2Pa sin(w) (ae a (x)\Gammaae min )
r
r
Or,
sin(w)
sin(w)
\Theta P
ab
ae a
x2Pa ae a (x)

cos(w)
\Theta P

Now, note that for system a
ab
ae a
x2Pa ae a (x)
Or,
p a
ab
ae a
x2Pa
ae a (x)
And likewise for system b. Substituting this into the
equation for - p yields:
By a similar series of steps, it can be shown that:
sin(w)(-n a \Gamma ae min )(N ab +N a )
r(N ab +N a +N b )
r(N ab +N a +N b )
Fusion Via a Linear Combination of Scores 13
After introducing the following shorthand for the relative
ratios of relevant and nonrelevant documents returned
by both systems:
N a +N ab
ab +N a +N b
ab +N a +N b
We have,
d =r
3.2.3. Maximizing d Because we have a formula
for d (the performance of the combined system), we
can find its maximum via calculus. Differentiating
with respect to w and setting it equal to 0 yields:
Or,
For simplicity, define ffi a as the numerator of this expression
and ffi b as the denominator so that tan(w opt
. Then the equation for the optimal weight could
equivalently be written:
sin(w opt
a
Recall from trigonometry that:
Using this fact, and the relationship between sin(w)
and cos(w) noted above, we get the following expression
for the performance of the optimally combined
system:
d opt =r4
At this point we make the simplifying assumption
that both systems have positive weight, a realistic one
if both systems perform reasonably well. Then the
above equation simplifies to:
3.2.4. Support for the 3 Hypotheses The final equation
from the previous section indicates that to maximize
d opt , we need to maximize both ffi a and ffi b . Remember
that,
ab )(-n a \Gamma ae min )
ab +N a +N b
Or, using shorthand,
14 Vogt and Cottrell
It is easy to show that since 0 - ff
ffi a is optimal when ff Similarly,
when -
a is maximal (i.e., when
d a is maximized). Similar arguments hold for
We are now in a position to address the three hy-
potheses: Linear combination is warranted when,
1. at least one system exhibits good performance,
2. both systems return similar sets of relevant documents

3. both systems return dissimilar sets of nonrelevant
documents.
The first point follows directly from the fact that ffi a and
are maximal when d a and d b are maximal. The second
two points can be concretely supported as follows.
Recall that ffi a is optimal when ff
Pa+P b +P ab
, it is equal to 1 when P
Likewise, are
optimal when both systems return no unique relevant
documents (i.e., they maximize the overlap of relevant
documents). Conversely, since ff
Na+N b +N ab
, it
goes to 0 as N b ! 1. The same argument holds for
are optimal when both systems are
retrieving different sets of nonrelevant documents.
3.2.5.

Summary

We have provided mathematical
support for our empirically derived conclusions about
when to use the linear model. Namely, when at least
one system exhibits good performance, both systems
return similar sets of relevant documents, and both systems
return dissimilar sets of nonrelevant documents.
These conclusions basically state that the LC model
primarily exploits only the Chorus Effect. We have
also derived a formula for the optimal weighting as
well as a formula for the performance of the combined
system assuming the optimal weighting.
4. Training the LC Model
We now turn to the practical side of things. In the previous
section we derived an optimal weighting for two
systems according to d. However, using this weighting
is not a practical technique for several reasons. First,
it is not general, in that it does not cover the case of
more than two systems. Second, it would be more satisfying
if we could choose a weight which optimizes a
more traditional IR performance measure, such as average
precision or exact precision. Finally, the optimal
weights used in the previous section were not tested
for generalization to new data. In this section, we describe
a series of experiments in which we compare
two different techniques for choosing the weights of
an LC model.
Fusion Via a Linear Combination of Scores 15
4.1. Advantages of Using d as an Optimization Cri-
terion
Recent work [Vogt and Cottrell, 1998b] has argued
in favor of using d 0 as an optimization measure for
ranking problems such as those seen in IR. The list of
reasons to prefer d 0 also apply to d. Namely,
ffl it is differentiable with respect to model parame-
ters, thus it can be applied to more complex models
(via gradient based techniques) than optimizing
precision directly, which has no gradient,
ffl it may be suitable for online learning,
ffl it is roughly correlated with other well-known
measures of performance like average precision,
ffl it is generally cheaper to calculate than rank-order
statistics, such as J [Bartell et al., 1994],
ffl it has an intuitive meaning: as a measure of how
well the scores on positive examples are separated
from those on negative examples.
Below we show that optimizing d to select a weighting
scheme for combining two IR systems works nearly
as well (as measured by average precision) as optimizing
average precision itself. It is important that we
distinguish between an optimization criterion and a
performance measure. Often, the same function plays
both roles. However, in the following experiments we
may choose the weights by optimizing either d or average
precision (P), but we will always evaluate the
resulting combined system using P.
4.2. Training a Model for the Routing Problem
As previously noted, the routing problem should be
easier for the LC model (or any parameterized model)
because a separate model can be trained for each query,
assuming enough training data. For this reason, we
begin by examining the routing problem.
4.2.1. Method We examined all 61 submissions to
the TREC5 adhoc track. For each of the possible
pairs, on each of the 50 TREC5 adhoc queries, and
70% of all possible documents, we chose w in one of
two ways:
ffl using a golden section search [Press et al., 1995]
to optimize P directly, or
ffl using a golden section search to optimize d directly

Golden section search does not require a gradient,
hence it is useful in both of these cases. Although
we are able to calculate the optimal weight for d using
equation (3), we use the golden section technique
because in the future we would like to be able to apply
the technique of optimizing d to models with more
than one parameter, for which an equation will not be
derivable.
We did not use a hold out set to stop training since the
LC model has only one parameter and thus is unlikely
to overfit the training data. We tested each of the trained
combinations on the remaining 30% of the documents,
evaluating each combination using P.
4.2.2. Results and Discussion For each of the
pair/query triples, we calculated
the difference between the value of average precision
on the test set as determined by the weight being trained
on d and the weight being trained on P. That is, we
are looking at the the quantity PP \Gamma P d . This measures
how much better training on P is than training on
d.

Figure

5 displays the histogram of this difference.
The average difference is -0.009. This means that on
average, training using d gives better generalization
when P is the measure of performance. Although an
ANOVA shows that the PP and P d distributions are
different (p ! 0:0001), to interpret whether or not this
is really a meaningful difference, consider a query that
has 75 relevant documents (the median for a TREC5
query). Then a difference of 0.009 in Pmeans that only
one or fewer more relevant documents are returned. It
is also interesting to note that there are a significant
number of combinations where training on d is better
than on P (differences less than zero).

Table

3 gives some idea as to the amount of improvement
gained by using the LC model. As noted
previously, the LC model is not always capable of
improving over the two component systems. Of the
91500 pair/query triples, 80324 (88%) saw improvement
on the training set over both of the component
systems when trained using P. Of those 80324, 32493
(36% of the total) also saw improvementon the test set.
The table also shows that over the 80324 combinations
which saw improvement on the training set, the average
degradation on the test set over the better of the two
component systems was 14%, a significant drop. The
fact that the LC model tends to degrade performance
for most pairs of systems should not be surprising -
recall the results of the previous section, which indicate
that the LC model should only be used in certain
situations. Apparently, training using d allows better
discrimination of when these situations arise. While
training on d results in fewer systems which see improvement
on the training set, it allows for much better
generalization when those weights are used on the test
data - in fact, it allows for an improvement in most
cases!
4.3. Training a Model for the Adhoc Problem
All of our analysis thus far has focused on the routing
problem. One can certainly argue that the adhoc
problem, where new queries are constantly being submitted
to the IR system, is also an important problem,
especially for the World Wide Web. The following
experiments explore this aspect of IR.
4.3.1. Method For the routing case we were able to
examine the full set of all the TREC5 queries. How-
ever, for the adhoc problem, we reduce the space of
Fusion Via a Linear Combination of Scores 1750001500025000-1 -0.8 -0.6 -0.4 -0.2 0
Fig. 5. Histogram of PP \Gamma P d on the Routing Test Set for 91500 TREC5 Combinations.

Table

3. Training Results for Routing
Training Test Combos Avg Degradation or
Method Improved Improved Improvement on Test
d 37661 (41%) 21028 (23%) +15%
Number of pair/query triples (out of 91500) which achieved better performance (as measured by P) than both component systems on the routing
problem. Average improvement on the test set is over all combinations counted in the first column.
combinations by only examining three subsets of the
total 61 systems. The first subset, labeled "chorus",
consists of 10 systems (see Table 4). These systems
were chosen because many of the 45 possible pairings
have a high overlap of relevant documents and low
overlap of nonrelevant documents, and thus are theoretically
able to exploit the linear combination model.
The second subset, labeled "diverse," was chosen to
maximize the differences between the systems in the

Table

4. Subsets Used in Adhoc Experiments
Subset Systems
chorus KUSG2 KUSG3 anu5man4 anu5man6 gmu96ma1
diverse CLTHES DCU961 anu5aut1 anu5man6 brkly17
random CLCLUS Cor5M2rf DCU961 ETHas1 ETHme1
subset. These differences were simply the average of
all the pairwise measures used our empirical analysis
above after they had all been normalized to z-scores.
Recall that these pairwise measures included the correlation
of scores, similarity of rank order as measured
by Guttman's point alienation statistic, and the size
of the intersection of the documents returned by both
systems. The third subset of ten systems was chosen
randomly from the 61 entries.
For each subset and each of the possible 45 pairs of
systems from that subset, w was chosen using golden
section search to maximize either -
d (P or d when
averaged over 35 randomly chosen queries). We then
tested each of the trained combinations on the 13 of the
remaining queries, evaluating each combination using
P.
4.3.2. Results and Discussion Once again, we use
d on the test set as our comparison metric.

Figure

6 displays histograms of this difference for the
chorus and random subsets (the diverse histogram is
similar to the one for chorus). The average difference
for the chorus subset is 0.012, diverse is 0.011, and
random is 0.006. This means that on average, training
using -
d gives worse generalization when -
P is the
measure of performance, just the opposite effect as
observed for routing. Once again, although these differences
are statistically significant, it is doubtful that
they are practically different.

Table

5 confirms that training the adhoc problem
using -
P is better than using -
d, since more pairs of
systems are able to successfully generalize and overall
degradation is less, although the difference is slight.
The table also confirms the hypothesis that adhoc is
harder to train than routing, since on average, there is a
degradation in performance. However, for a significant
number of combinations (16% or 23%) there was an
improvement. In future work, we would like to apply
techniques similar to those we used in our empirical
work for routing in order to predict when improvement
is achievable for the adhoc task.
5. Conclusions
Our analysis of the linear combination of scores fusion
model has revealed a number of important points.
The LC model has severe limitations, both in scope
and power. Its effective use is limited to situations
where the systems involved have high overlap of rel-
Fusion Via a Linear Combination of Scores 1951525
Fig. 6. Histogram of -
d on the Adhoc Test Set for the chorus (left) and random (right) subsets

Table

5. Training Results for Adhoc
Training Test Combos Avg Degradation
Subset Method Improved Improved on Test
chorus -
diverse -
random -
Total/average
chorus -
d 19 (42%) 5 (11%) -15%
diverse -
d
random -
d
Total/average 61 (45%) 21 (16%) -10%
Number of system pairs (out of 45) which achieved better performance (as measured by -
P) than both component systems on the adhoc problem.
Average degradation on the test set is over all combinations counted in the first column.
evant documents and low overlap of nonrelevant doc-
uments. Luckily, we have also developed a technique
which can very accurately (r predict when
improvement is possible for the routing problem.
Our analysis has also revealed several advantages
and disadvantages to using d as a performance crite-
20 Vogt and Cottrell
rion. Despite the facts that it fails to take into account
recall, and its correlation with average precision
is weak, its simple algebraic form has allowed us to
mathematically support conclusions about the model
which previously were only empirically based, and to
derive theoretically optimal weightings for pairs of IR
systems. Furthermore, when used as an optimization
criterion for the routing problem, d selects weights
which generalize much better than those chosen by
optimizing average precision, resulting in an average
improvement of 15% versus an average degradation of
14% when training average precision directly. Further-
more, on the adhoc problem, training d works about
as well as training average precision. Because d is
also differentiable and cheap to calculate, it is also a
likely candidate for use in gradient based optimization
procedures, which will be necessary for combinations
of more than two systems or for other parameterized
models (e.g., neural nets).



--R

Automatic combination of multiple ranked retrieval sys- tems
Combining evidence of multiple query representations for information retrieval.
A neural network model for documentary base self-organising and querying
Comparing neural and probabilistic relevance feedback in an interactive information retrieval system.

Indexing by latent semantic analysis.
Information retrieval using dynamic evidence combination.
The Third Text REtrieval Conference (TREC-3)
The Fifth Text REtrieval Conference (TREC-5)
Decision level data fusion for routing of documents in the TREC3 context: A best case analysis of worst case results.

SIGIR 93:
Analyses of multiple evidence com- bination
Numerical Recipes in C: The Art of Scientific Computing.

Combination of multiple searches.
Signal detection theory and ROC Analysis in Psychology and Diagnostics.
Information Re- trieval





Computation of term associations by a neural network.

--TR

--CTR
Javed A. Aslam , Mark Montague, Bayes optimal metasearch: a probabilistic model for combining the results of multiple retrieval systems (poster session), Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.379-381, July 24-28, 2000, Athens, Greece
Elmrio Gomes Dutra, Jr. , Jose Valdeni de Lima, Supplement of partial ranks to the data fusion, Proceedings of the 12th Brazilian symposium on Multimedia and the web, November 19-22, 2006, Natal, Rio Grande do Norte, Brazil
Shengli Wu , Fabio Crestani, Methods for ranking information retrieval systems without relevance judgments, Proceedings of the ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
Anselm Spoerri, Using the structure of overlap between search results to rank retrieval systems without relevance judgments, Information Processing and Management: an International Journal, v.43 n.4, p.1059-1070, July, 2007
Holger Billhardt , Daniel Borrajo , Vctor Maojo, Using genetic algorithms to find suboptimal retrieval expert combinations, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain
Eui-Hong Han , George Karypis , Doug Mewhort , Keith Hatchard, Intelligent metasearch engine for knowledge management, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
M. Elena Renda , Umberto Straccia, Web metasearch: rank vs. score based rank aggregation methods, Proceedings of the ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
David Lillis , Fergus Toolan , Rem Collier , John Dunnion, Probabilistic data fusion on a large document collection, Artificial Intelligence Review, v.26 n.1-2, p.23-34, October   2006
Shengli Wu , Fabio Crestani, Shadow document methods of resutls merging, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
Paul Ogilvie , Jamie Callan, Combining document representations for known-item search, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada
Holger Billhardt , Daniel Borrajo , Victor Maojo, Learning retrieval expert combinations with genetic algorithms, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.11 n.1, p.87-113, February
Kui Lam Kwok , Sora Choi , Norbert Dinstl, Rich results from poor resources: NTCIR-4 monolingual and cross-lingual retrieval of korean texts using chinese and english, ACM Transactions on Asian Language Information Processing (TALIP), v.4 n.2, p.136-162, June 2005
Dmitri Roussinov , Weiguo Fan, Discretization based learning approach to information retrieval, Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, p.153-160, October 06-08, 2005, Vancouver, British Columbia, Canada
Sally McClean, Performance prediction of data fusion for information retrieval, Information Processing and Management: an International Journal, v.42 n.4, p.899-915, July 2006
David Lillis , Fergus Toolan , Rem Collier , John Dunnion, ProbFuse: a probabilistic approach to data fusion, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA
Kui-Lam Kwok , Laszlo Grunfeld , Peter Deng, Employing web mining and data fusion to improve weak ad hoc retrieval, Information Processing and Management: an International Journal, v.43 n.2, p.406-419, March 2007
Mark Montague , Javed A. Aslam, Relevance score normalization for metasearch, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA
B. Uygar Oztekin , George Karypis , Vipin Kumar, Expert agreement and content based reranking in a meta search environment using Mearf, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA
D. Lillis , F. Toolan , A. Mur , L. Peng , R. Collier , J. Dunnion, Probability-based fusion of information retrieval result sets, Artificial Intelligence Review, v.25 n.1-2, p.179-191, April     2006
D. Frank Hsu , Isak Taksa, Comparing Rank and Score Combination Methods for Data Fusion in Information Retrieval, Information Retrieval, v.8 n.3, p.449-480, May 2005
Yu-Ting Liu , Tie-Yan Liu , Tao Qin , Zhi-Ming Ma , Hang Li, Supervised rank aggregation, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
Steven M. Beitzel , Eric C. Jensen , Abdur Chowdhury , David Grossman , Ophir Frieder , Nazli Goharian, Fusion of effective retrieval strategies in the same information retrieval system, Journal of the American Society for Information Science and Technology, v.55 n.10, p.859-868, August 2004
Weiguo Fan , Ming Luo , Li Wang , Wensi Xi , Edward A. Fox, Tuning before feedback: combining ranking discovery and blind feedback for robust retrieval, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom
Fabio Crestani , Shengli Wu, Testing the cluster hypothesis in distributed information retrieval, Information Processing and Management: an International Journal, v.42 n.5, p.1137-1150, September 2006
Weiguo Fan , Michael D. Gordon , Praveen Pathak, A generic ranking function discovery framework by genetic programming for information retrieval, Information Processing and Management: an International Journal, v.40 n.4, p.587-602, May 2004
Javed A. Aslam , Mark Montague, Models for metasearch, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.276-284, September 2001, New Orleans, Louisiana, United States
Sally McClean, Result merging methods in distributed information retrieval with overlapping databases, Information Retrieval, v.10 n.3, p.297-319, June      2007
Cai-Nicolas Ziegler , Sean M. McNee , Joseph A. Konstan , Georg Lausen, Improving recommendation lists through topic diversification, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan
Sally McClean, Improving high accuracy retrieval by eliminating the uneven correlation effect in data fusion, Journal of the American Society for Information Science and Technology, v.57 n.14, p.1962-1973, December 2006
Mark Montague , Javed A. Aslam, Condorcet fusion for improved retrieval, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
Weiguo Fan , Michael Gordon , Praveen Pathak, On linear mixture of expert approaches to information retrieval, Decision Support Systems, v.42 n.2, p.975-987, November 2006
Wai-Kit Lo , Helen Meng , P. C. Ching, Cross-language spoken document retrieval using HMM-based retrieval model with multi-scale fusion, ACM Transactions on Asian Language Information Processing (TALIP), v.2 n.1, p.1-26, March
Jacques Savoy, Comparative study of monolingual and multilingual search models for use with asian languages, ACM Transactions on Asian Language Information Processing (TALIP), v.4 n.2, p.163-189, June 2005
Weiyi Meng , Clement Yu , King-Lup Liu, Building efficient and effective metasearch engines, ACM Computing Surveys (CSUR), v.34 n.1, p.48-89, March 2002
routing;fusion;performance evaluation;neural networks;linear combination