Fusion of Retrieval Models at CLEF 2008 Ad-Hoc Persian Track

Abstract

Metasearch engines submit the user query to several underlying search engines and then merge their retrieved results to generate a single list that is more effective to the users' information needs. According to the idea behind metasearch engines, it seems that merging the results retrieved from different retrieval models will improve the search coverage and precision. In this study, we have investigated the effect of fusion of different retrieval techniques on the performance of Persian retrieval. We use an extension of Ordered Weighted Average (OWA) operator called IOWA and a weighting schema, NOWA for merging the results. Our experimental results show that merging by OWA operators produces better precision.

Introduction

With the rapid growth of the volume of the data, improving the effectiveness of information retrieval systems is essential. Many approaches and methods have developed to exhibit better retrieval engines [ 1 ]. In this study, we try to use the idea behind metasearch engines in order to improve the results of Persian information retrieval. We consider each retrieval model as a decision maker and then fuse their decisions with an OWA operator in order to increase the effectiveness.

This work has been done as our first participation in the CLEF evaluation campaign. For the Ad-Hoc Persian track we submitted eleven experiments (runs): UTNLPDB3BB2, UTNLPDB3BM25, UTNLPDB3DFR, UTNLPDB3IFB2, UTNLPDB3INEXPB2, UTNLPDB3INEXPC2, UTNLPDB3INL2, UTNLPDB3PL2, UTNLPDB3TFIDF, UTNLPDB3NOWA and UTNLPDB3OWA.

Our main goal was to study the effect of fusion operators and whether fusing retrieval models can bring additional performance improvements. The collection that is used in this study is a standard test collection of Persian text which is called Hamshahri and was made available to CLEF by University of Tehran [ 2 ], [ 3 ]. In section two, we present a brief description of the retrieval methods that have been used in our experiments. Previous experiments have demonstrated that these methods have good performance on Persian retrieval. In section three, OWA operator and its extensions that are used for merging the results are described. One key point in the OWA operator is to determine its associated weights. In this study, we use a weighting model which is based on Normal distribution and an IOWA extension. There are two approaches to fuse the retrieved lists: • Combine the results of distinct retrieval methods.

• Combine the results of the same method but with different types of tokens Runs that submitted to CLEF 2008 use the first approach and results show that using this approach dose not lend itself to a significant improvement. It seems although the retrieval methods are different but their performance and result set is similar. In another word, those retrieval methods provide the same vision of the data. After BB2 BM25 IFB2

In_expB2

In_expC2 InL2 PL2 TF_IDF

DFR_BM25

The DFR version of BM25 CLEF results were published, we tried the second approach and we were able to improve the effectiveness up to 5.67% and reached the 45.22% average precision on test set. Section four describes the experiments and their results.

Retrieval Methods

In this work, for the purpose of fusion, we needed different retrieval methods. After studying different retrieval toolkits, finally we choose Terrier [ 4 ]. Different methods have been implemented in Terrier toolkit. Among these methods, we selected nine of them. The weighting models and a brief description of them (from [ 5 ]) are illustrated in table 1. Table 2 depicts the result obtained from running the above nine methods described in Table 1 on the training set of queries.

Bose-Einstein model for randomness, the ratio of two Bernoulli's processes for first normalization, and Normalization 2 for term frequency normalization

The BM25 probabilistic model Inverse Term Frequency model for randomness, the ratio of two Bernoulli's processes for first normalization, and Normalization 2 for term frequency normalization

Inverse expected document frequency model for randomness, the ratio of two Bernoulli's processes for first normalization, and Normalization 2 for term frequency normalization Inverse expected document frequency model for randomness, the ratio of two Bernoulli's processes for first normalization, and Normalization 2 for term frequency normalization with natural logarithm Inverse document frequency model for randomness, Laplace succession for first normalization, and Normalization 2 for term frequency normalization Poisson estimation for randomness, Laplace succession for first normalization, and Normalization 2 for term frequency normalization The tf*idf weighting function, where tf is given by Robertson's tf and idf is given by the standard Sparck Jones' idf

OWA Fuzzy Operator

This section describes the Order Weighted Average (OWA) operator, normal distribution-based weighting and IOWA extension. 3.1.

OWA Definition

An OWA operator of dimension n is a mapping, OWA: R n → R , that has an associated n vector n w = (w1, w2 ,..., wn )T such that w j ∈ [ 0,1 ] and ∑ w j = 1 . Furthermore, j=1

n OWA(a, a,..., a) = ∑ b w

j j j=1 Where b j is the jth largest element of the collection of the aggregated objects a1, a2 ,..., an [ 6 ]. 3.2.

IOWA

An IOWA operator is defined as follows:

n IOWA( u1, a1 , u2 , a2 ,..., un , an ) = j∑=1 w j b j , w = (w1, w2 ,..., wn ) T where is a weighting vector, such j=1 3.3.

NOWA

n that ∑ w j = 1 , 0 ≤ w j ≤ 1 and b j is the ai value of the OWA pair ui , ai having the jth largest ui , and ui in ui , ai is referred to as the order inducing variable and ai as the argument variable. It is assumed that ai is an exact numerical value while ui can be drawn from any ordinal set Ω [ 7 ].

Suppose that we want to fuse n preference values provided by n different individuals. Some individuals may assign unduly high or unduly low preference values to their preferred or repugnant objects. In such a case, we shall assign very low weights to these “false” or “biased” opinions, that is to say, the closer a preference value (argument) is to the mid one(s), the more the weight it will receive; conversely, the further a preference value is from the mid one(s), the less the weight it will have [ 8 ].

Let w = (w1, w2 ,..., wn )

T be the weight vector of the OWA operator; then we define the following: . wi =

1 2πσ n e −[(i−µ n )2 2σ n2 ] , Where µ n is the mean of the collection of1,2,..., n , and σ n (σ n > 0) is the standard deviation of the collection of1,2,..., n . µ n andσ n are obtained by the following formulas, respectively: µ n = σ n = 1 n(n + 1) n 2 = 1 ∑n (i − µ n ) 2 j=1 n Consider that ∑ w j = 1 and 0 ≤ w j ≤ 1 then we have: wi = n ∑ j=1

1 2πσ n

1 2πσ n e −[(i−µn )2 2σ n2 ] e −[( j−µn )2 2σ n2 ] = j=1 e −[(i−µn )2 2σ n2 ] n ∑ e −[( j−µn )2 2σ n2 ] , i = 1,2,..., n

Experiment

For the experiments, CLEF has obtained the standard Persian test collection which is called Hamshahri. Hamshahri collection is the largest test collection of Persian text. This collection is prepared and distributed by University of Tehran. The third version of Hamshahri collection is 600MB in size and contains more than 160,000 distinct textual news articles in Persian [ 9 ]. There were 50 training queries with their relevance judgments and 50 test queries prepared for the Persian ad-hoc track.

For the CLEF, we choose nine methods of document retrieval described above and fuse the top hundred retrieved results from each of them.

We use OWA operator based on normal distribution weighting for merging the lists. In this problem, we have nine decision makers, so the weighting vector is as the following: n = 9, µ 9 = 5,σ 9 = 20 , ornes(w) = 0.5, disp(w) = 2.1195,

3 The precision-recall diagram obtained after submitting the OWA run to CLEF is illustrated in figure 1. IOWA extension was also tested. We used 50 training queries in order to calculate the weighting vector for this method. We ran the nine selected retrieval methods on the collection. The following weighting vector is obtained by using the average precision of each method as its weight: {0.4167/3.8409, 0.4009/3.8409, 0.4347/3.8409, 0.4328/3.8409, 0.4329/3.8409, 0.4461/3.8409, 0.42/3.8409, 0.4548/3.8409, 0.402/3.8409} (3.8409 is the sum of the obtained average precisions) Figure 2 illustrates the precision-recall diagram of IOWA run with the above weighting vector.

Analyzing the Results and More Experiments

We submitted top hundred retrieved documents for our runs to CLEF, while CLEF evaluates the results by top thousand documents which decreased average precision about 10% in average. Therefore, in future we intend to calculate our Precision-Recall charts and other measurements based the top thousand retrieved documents. The results published by CLEF for our fusion runs show that using fusion techniques on these methods does not yield to improved results over the individual methods. By analyzing the lists obtained from the retrieval methods, we observed that these result lists for these nine different methods have high overlap among them. On the other hand, fusion methods work well when there are significant differences between decision makers. Therefore, we have concluded that although the methods are different they are not significantly different from each other and basically they provide the same view of the collection.

After the CLEF results were published, we decided to investigate the second approach for fusion and look into the effect of different tokens in retrieval. For this purpose we chose a vector space model and ran it on the training set three times with three different types of tokens namely 4-grams, stemmed single terms and unstemmed single terms. To obtaining best results, we ran PL2 method of terrier toolkit on 4gram terms, indri of lemur toolkit [ 10 ] on stemmed terms and TF_IDF of terrier toolkit on unstemmed terms. Then we applied the above OWA methods and as shown in table 3, we obtained 9.97% improvements over individual runs. After that, we continued this approach and did more experiments with the CLEF test set. On the test set, this approach lead only to 5.67% improvements on the average precision over individual runs using NOWA method and 5.6% using IOWA method. Table 4, figure 3 and figure 4 demonstrate the obtained results.

Conclusion

Our motivation for participation in the Ad-Hoc Persian track of CLEF was investigating the influence of fusion techniques on the effectiveness of Persian retrieval methods. First we use nine retrieval methods and then fuse the results by NOWA and IOWA. The obtained results showed that functionality of these methods have high overlap and there were no considerable improvement by applying fusion techniques. In the second stage, we changed our approach to use different versions of a same method. To reach this goal, we focused on working with different terms instead of different methods. Results indicates fusion techniques works well on the circumstances which the decision makers have different views.

In future, we will investigate the effects of different token types and retrieval engines on Persian retrieval and will try to fine tune an engine based on fusion.

References

[1] Ian H. Witten , Alistair Moffat and Timothy C. Bell . Managing Gigabytes: Compressing and Indexing Documents and Images . Morgan Kaufmann Publishers, Los Altos, USA, 1999

[2] Oroumchian F , Darrudi E . Experiments with Persian Text Compression for Web . WWW 2004 .

[3] http://ece.ut.ac.ir/dbrg/hamshahri/

[4] http://ir.dcs.gla.ac.uk/terrier/

[5] http://ir.dcs.gla.ac.uk/terrier/doc/configure_retrieval.html

[6] Yager RR . On ordered weighted averaging aggregation operators in multicriteria decision making . IEEE Trans Syst Man Cybern 1988 ; 18 : 183 - 190 .

[7] Yager RR , Filev D.P. Induced ordered weighted averaging operators . IEEE Transactions on Systems, Man, and Cybernetics--Part B 29 ( 1999 ) 141 - 150 .

[8] Xu Z. Induced uncertain linguistic OWA operators applied to group decision making . International Journal of Intelligent Systems , Vol. 20 , 843 - 865 ( 2005 ).

[9] Amiri H , Aleahmad A , Oroumchian F , Lucas C , Rahgozar M. Using OWA Fuzzy Operator to Merge Retrieval System Results, 2007

[10] http://www.lemurproject.org/indri/