We explore the use of state of the art query expansion techniques combined with a new family of ranking functions which can take into account some semantic structure in the query. This structure is extracted from WordNet similarity measures. Our approach produces improvements over the baseline and over query expansion methods for a number of performance measures including GMAP.
Exploiting semantic information for information retrieval is known to be very hard. One of the problems, in our opinion, is the term independence hypothesis. A second problem is that of querydependant semantics: two terms semantically related in a query may not be so in the next. We try to address these two problems. We propose to make explicit some of the term dependence information using a form of structured query (which we call query clauses), and to use a ranking function capable of taking the structure information into account. We combine the use of query expansion techniques and semantic disambiguation to construct the structured queries that are both semantically rich and focused on the query.
R(q,d) =
X t en q k1((1 idf (t) =
tftd b) + b alvdld ) + tftd
idf (t) N
df (t) + 0:5 df (t) + 0:5 (1) (2) For all our experiments we used Lucene1, modifying the raking functions as needed. 1.2
Our rst approach is to apply state of the art query expansion methods. We selected two methods which we nd very e ective. 1.3
One of the most interesting approaches based on term distribution analysis has been proposed by C. Carpineto et. al. [2], and uses the concept the Kullback-Liebler Divergence [3] to compute the divergence between the probability distributions of terms in the whole collection and in the top ranked documents obtained for a rst pass retrieval using the original user query. The most likely terms to expand the query are those with a high probability in the top ranked set and low probability in the whole collection. For the term t this divergence is: w(t) = PR(t)log
PR(t)
PC (t) qtw =
qtf qtfmax +
w(t) wmax(t) where w(t) is the original expansion weight of term t, wmax(t) is the maximum w(t) of the expanded query terms, is a parameter, qtf is the frequency of the term t in the query and qtfmax is the maximum term frequency in the query q. In all our experiments, is set to 0.3. where PR(t) is the probability of the term t in the top ranked documents, and PC (t) is the probability of the term t in the whole collection. 1.4
The Divergence From Randomness (DFR) [1] term weighting model infers the informativeness of a term by the divergence between its distribution in the top-ranked documents and a random distribution. The most e ective DFR term weighting model is the Bo1 model that uses the BoseEinstein statistics [8, 6]: w(t) = tfx log2(
) + log(1 + Pn) 1 + Pn
Pn where tfx is the frequency of the query term in the x top-ranked documents and Pn is given by F , where F is the frequency of the query term in the collection and N is the number of documents N in the collection.
We have used the rst document retrieved for term extraction. The number of terms used to expand the original query has been 40. 1.5
After the list of candidate terms has been generated by one of the methods described above, the selected terms which will be added to the query must be re-weighted. Di erent schemas have been proposed for this task. We have compared these schemas and tested which is the most appropriate for each expansion method and for our combined query expansion method.
The classical approach to term re-weighting is the Rocchio algorithm [
Query expansion is known to degrade the performance of some queries. In order to alleviate this problem we experimented with query quality predictors [4]. For e ciency reasons we only consider pre-retrieval methods. In particular, we used the AvICTF predictor proposed by [5]: AvICT F = log2 Qt2Q ICT F ql = log2 Qt2Q FT ql (6) where T is the number of tokens in the collection. The predictor is used as follows. We compute the AvICTF value of the expanded query. If this value is above a certain threshold (9.0) we will use the expanded query. Otherwise we use the original query. The threshold was found empirically on the training corpus. 2
In table 1 we report results on the baseline and query expansion for several evaluation measures, including GMAP which is perhaps the most interesting in the context of robust retrieval.
MAP .3614 .3833 .3835 .3811
As we can see, the query expansion methods obtain some improvement over the baseline, for all linear average measures, but not for GMAP. As it is usually the case, the query expansion methods are hurting the performance of the hardest queries. AvICTF it is helping somewhat but not enough to improve over the baseline. 3
Simply adding terms to a query may not be the best way to enrich them. We believe that adding
related terms worsens the term independence hypothesis. In this section we explore an alternative
family of ranking functions that addresses this issue. This scoring method is inspired in the elded
version of BM25 proposed in [
Related terms are grouped in sets called clauses, and queries are de ned as sets of clauses. Terms within the clauses and clauses themselves may be weighted. Each clause is considered as a pseudo term with each own tf and idf :
n score(d; qc) = X 2In the original formulation [7] tf (ci; d) was de ned as a weighted sum, taking wt into account. This is more general and makes more sense from a theoretical point of view. However, for this task we observed better results if we dropped the weights. They are only used in the computation of Eidf . This needs further investigation.
We replace the idf term by a clause idf, de ned as the expected idf of a term in the clause: Eidf (c; d) = Pt02c wt0 tf (d; t0) (t;wt)2c
X 1 wt tf (d; t) idf (t) (8) This has several nice properties, for example terms added with very small weights have very small e ect on the clause idf , and terms not occurring in the document have no e ect at all. See [7] for more details and a comparaison to other solutions. However, it has the dissadvantage that it needs to be computed for every clause in every document, at query time, unlike idf which can be pre-computed for each term.
This scoring method provides a method to introduce into the ranking function the expanded terms without the need of Rocchio. The question remains how to construct the clauses. Our hypothesis is that semantically related terms should be grouped in clauses. The CLEF corpus is ideal to test this hypothesis since all the terms in it have be annotated with their corresponding synset in WordNet. Our approach is described in the next section. 3.1
We need to construct a structured query from the initial user query. We have explored many possibilities, most of which lead to bad results (worse than simple expansion). We describe here the method used for our CLEF submission, which was quite successful.
In our experience state of the art query expansion methods are superior than semantic expansion methods based on WordNet or corpus statistics; their main advantage is that they lead to expansions that are truly query dependant; semantic information tends to be too vague and it is hard to use without knowing the context in which a word is used. However, the idea behind our method is that query expansion and semantic information may be used complementary. In particular, semantic information may be useful to decide the semantic query structure (query clauses in our case).
We proceed as follows. First we assign to each original query term a di erent query clause (we assume query terms to be independent in the traditional way). We assign the weight of 1 to these terms. Then we do standard query expansion and select the usual number of expansion terms (40 in our case) for the query. We use the DFR Bo1 method for this, although similar results can be obtained with the other methods. We then compute a semantic similarity between each original query word and each expansion word (discussed below). If this similarity is above a threshold , we include the expanded term in the clause of the original term; we assign to this term a weight equal its expansion weight. All the expanded terms remaining are grouped into an extra query clause. This way, the number of clauses is always equal to jqj + 1.
As an example, let's say that the original query was a; b and the terms c; d; e were found to be good expansion terms, with weights wc; wd; we respectively. After computing the 6 semantic distances between original and expanded terms, we would check which were above a threshold . Say for example that only d was su ciently similar to b, all other similarities being bellow . Then we would end up with the query:
f f(a; 1)g; f(b; 1); (d; wd)g; f(c; wc); (e; wd)gg
Semantic similarities are computed based on WordNet. There exists an extensive literature on
measures of semantic similarity. We have used the WordNet Similarity3 package, which contains
many semantic measures. In particular we used (after some experimentation) the wup measure
[
We report here results on the semantic clause method described above.
We can see that the proposed method improves results over the baseline and over query expansion, for all relevance measures including GMAP. This is very encouraging because it is one of the few results to our knowledge that show that WordNet information and WSD can be used to improve ad-hoc retrieval in an open domain.
Note that increasing values of lead to increasing results4; however = 1 lead to poor results during the testing phase and was not submitted. This is somewhat surprising, reinforces the idea that one must be very conservative in query expansion in order to be robust. This requires further investigation. Further evidence of the robustness of our method is the fact that the use of AvICTF was not found useful.
In our opinion a bottleneck to further improve performance is in the creation of high quality structures. WordNet Similarity methods tend to produce noisy clauses, often putting in correspondence terms that are not related in the context of the query. [1] Gianni Amati and Cornelis Joost Van Rijsbergen. Probabilistic models of information retrieval based on measuring the divergence from randomness. ACM Trans. Inf. Syst., 20(4):357{389, 2002. [2] Claudio Carpineto, Renato de Mori, Giovanni Romano, and Brigitte Bigi. An informationtheoretic approach to automatic query expansion. ACM Trans. Inf. Syst., 19(1):1{27, 2001. [3] Thomas M. Cover and Joy A. Thomas. Elements of information theory. Wiley-Interscience,
New York, NY, USA, 1991. [4] Ben He and Iadh Ounis. Query performance prediction. Inf. Syst., 31(7):585{594, 2006. [5] K. L. Kwok. Experiments with a component theory of probabilistic information retrieval based on single terms as document components. ACM Trans. Inf. Syst., 8(4):363{386, 1990. [6] C. Macdonald, B. He, V. Plachouras, and I. Ounis. University of Glasgow at TREC 2005: Experiments in Terabyte and Enterprise Tracks with Terrier. In Proceeddings of the 14th Text REtrieval Conference (TREC 2005), 2005. [7] Jose R. Perez-Aguera, Hugo Zaragoza, and Lourdes Araujo. Exploiting morphological query structure using genetic optimisation. In NLDB, pages 124{135, 2008. [8] V. Plachouras, B. He, and I. Ounis. University of Glasgow at TREC2004: Experiments in Web, Robust and Terabyte tracks with Terrier. In Proceeddings of the 13th Text REtrieval Conference (TREC 2004), 2004.
4Note that query inclusion requires that similarity is greater than , so even for assigned to clauses. = 0 many terms are not