Abstract

This paper presents work on document retrieval for Italian carried out at ITC-irst. Two different approaches to information retrieval were investigated, one based on the Okapi weighting formula and one based on a statistical model. Development experiments were carried out using the Italian sample of the TREC-8 CLIR track. Performance evaluation was done on the Cross Language Evaluation Forum (CLEF) 2000 Italian monolingual track.

INTRODUCTION

TEXT PREPROCESSING

Document and query preprocessing implies several stages: tokenization, morphological analysis of words, part-of-speech (POS) tagging of text, base form extraction, stemming, and stop-terms removal.

Tokenization. Tokenization of text is performed in order to isolate words from punctuation marks, recognize abbreviations and acronyms, correct possible word splits across lines, and discriminate between accents and quotation marks.

Morphological analysis. A morphological ana

lyzer decomposes each Italian inflected word into its morphemes, and suggests all possible POSs and base forms of each valid decomposition. By base forms we mean the usual not inflected entries of a dictionary.

POS tagging. POS tagging is based on a Viterbi decoder that computes the best text-POS alignment on the basis of a bigram POS language model and a discrete observation model (Merialdo, 1994) . The employed tagger works with 57 tag classes and has an accuracy around 96%.

Base form extraction. Once the POS and the

morphological analysis of each word in the text is computed, a base form can be assigned to each word.

Stemming. Word stemming is applied at the level of tagged base forms. POS specific rules were developed that remove suffixes from verbs, nouns, and adjectives.

Stop-terms removal. Words in the collection that are considered non relevant for the purpose of information retrieval are discarded in order to save index space. Words are filtered out on the basis either of their POS or their inverted document frequency. In particular, punctuation is eliminated together with articles, determiners, quantifiers, auxiliary verbs, prepositions, conjunctions, interjections, and pronouns. Among the remaining terms, those with a low inverted document frequency, i.e. that occur in many different documents, are eliminated.

An example of text preprocessing is presented in Table 8.

Terms

text base forms stems base forms stems Stop no no no yes yes

3. INFORMATION RETRIEVAL MODELS

w number of documents containing w frequency of in the collection d length of document w q frequency of in query w d frequency of word in document d vocabulary size of document length of the collection mean document length number of documents average document vocabulary size vocabulary size of the collection V 160K 126K 101K 125K 100K d evance of a document versus a query q. In this

3.1. Okapi Model

Okapi (Robertson et al., 1994) is the name of a retrieval system project that developed a family of weighting functions in order to evaluate the relwork, the following Okapi weighting function was applied: P (q j d) where represents the likelihood of q, given P (d) d, represents the a-priori probability of d, and P (q) is a normalization term. By assuming no ad q the probability of generating and assume an priori knowledge about the documents, and disregarding the normalization factor, documents can be ranked, with respect to q, just by the likelihood term. If we interpret the likelihood function as order-free multinomial model, the following logprobability score can be derived: w The probability that a term is generated by d can be estimated by applying statistical language modeling techniques. Previous work on statistical information retrieval (Miller et al., 1998; Ng, 1999) proposed to interpolate relative frequencies of each document with those of the whole collection, with interpolation weights empirically estimated from the data.

In this work we use an interpolation formula which applies the smoothing method proposed by (Witten and Bell, 1991) . This method linearly smoothes word frequencies of a document and the amount of probability assigned to never observed terms is proportional to the number of different words contained in the document. Hence, the following probability estimate is applied: Vd 134 129 126 80 77 (3) (1) (2) where: k1(1 fd(w)

Vd mAvPr

Data Set (topic #s’)

CLIR (54-81) title description narrative CLEF (1-40) title description narrative Min 41 3 8 25 31 3 7 14

EXPERIMENTS

(8) (9) B ing all the terms of the top documents according T documents are taken and the most relevant terms in them are added to the query. Hence, the retrieval phase is repeated with the augmented query. In this work, new search terms are extracted by sortto (Johnson et al., 1999) : r 1 : : : provided against a given query q, let rk q The AvPr for is defined as the average of the pre

This section presents work done to develop and test the presented models. Development and testing were done on two different Italian document retrieval tasks. Performance was measured in terms of Average Precision (AvPr) and mean Average Precision (mAvPr). Given the document ranking be the ranks of the retrieved relevant documents. cision values achieved at all recall points, i.e.:

The mAvPr of a set of queries corresponds to the mean of the corresponding query AvPr values.

4.1. Development

For the purpose of parameter tuning, development material made available by CLEF was used.

4.3. Blind Relevance Feedback Tuning

1CLIR topics without Italian relevant documents are 60, 63, 76, and 80.

B 0.7 0

5 0.6 0.5 T = 15 were chosen, whose combination gives B = 5 uments and the number of relevant terms ters is shown. Finally, the number of relevant doca mAvPr of 49.2%, corresponding to a 6.8% improvement over the first step.

Further work was done to optimize the performance of the first retrieval step. Indeed, performance of the BRF procedure is determined by the precision achieved, by the first retrieval phase, on the very top ranking documents. In particular, an higher resolution for documents and queries was considered by using base forms instead of stems.

In Table 6 mAvPr values are shown by considering different combinations of text preprocessing before and after BRF. In particular, we considered using base forms before and after BRF, using word stems before and after BRF, and using base forms before BRF and stems after BRF. The last combination achieved the largest improvement (8.6%) and was adopted for the final system. of the topics do not have corresponding documents in the collection they are not taken into account 2.

More details about the CLEF collection and topics are in Tables 3, 4, and 5.

Official results of the Okapi and statistical models are reported in Figure 3 with the names irst1 and irst2, respectively. Figure 3 shows the difference in AvPr between each run and the median reference provided by the CLEF organization. As a further reference, performance differences between the best result of CLEF and the median are also plotted. The mAvPr of irst1 and irst2 are 49.0% and 47.5%, respectively. Both methods score above the median reference mAvPr, which is 44.5%. The mAvPr of the median reference was computed by taking the average over the median AvPr scores.

I st ba ba

II st ba st

5 46.4 46.2 46.7

4.4. Official Evaluation

The two presented models were evaluated on the CLEF 2000 Italian monolingual track. The test collection consists of newspaper articles published by La Stampa, during 1994, and 40 topics. As six 5. IMPROVEMENTS r(B(d))]2 (10) 2CLEF topics without Italian relevant documents are 3, 6, 14, 27, 28, and 40. 35 merge best 0.7 0 0.6

S By taking the average of over all the queries 3, S 1=(N and B, has mean 0 and variance 1). On [0; 1] of each model were normalized in the range A Under the hypothesis of independence between the contrary, in case of perfect correlation the S statistics has value 1. a rank correlation of 0.4 resulted between the irst1 and irst2 runs.

This results confirms some degree of independence between the two information retrieval models. Hence, a combination of the two models was implemented by just taking the sum of scores. Actually, in order to adjust scale differences, scores before summation. By using the official relevance assessments of CLEF, a mAvPr of 50.0% was achieved by the combined model.

In Figure 4 and Figure 5 detailed results of the combined model (merge) are provided for each query, respectively, against the CLEF references and the irst1 and irst2 runs. It results that the combined model performs better than the median reference on 24 topics of 34, while irst1 and irst2 improved the median AvPr 16 e 17 times, respectively. Finally, the combined model improves the best reference on two topics (20 and 36). 30 35 merge vs. irst1 merge vs. irst2 -0.4 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39

Topic Number

References

Federico , Marcello, 2000 . A system for the retrieval of italian broadcast news . Speech Communication , 33 ( 1 - 2 ).

Federico , Marcello and Renato De Mori, 1998 . Language modelling . In Renato De Mori (ed.), Spoken Dialogues with Computers, chapter 7 . London, UK: Academy Press.

Johnson , S.E. , P. Jourlin , K. Spark Jones , and P.C. Woodland , 1999 . Spoken document retrieval for TREC- 8 at Cambridge University. In Proceedings of the 8th Text REtrieval Conference . Gaithersburg, MD.

Merialdo , Bernard, 1994 . Tagging English text with a probabilistic model . Computational Linguistics , 20 ( 2 ): 155 - 172 .

Miller , David R. H. , Tim Leek , and Richard M. Schwartz , 1998 . BBN at TREC-7: Using hidden Markov models for information retrieval . In Proceedings of the 7th Text REtrieval Conference . Gaithersburg, MD.

Mood , Alexander M. , Franklin A. Graybill , and Duane C. Boes , 1974 . Introduction to the Theory of Statistics. Singapore: McGraw-Hill .

Ng , Kenney, 1999 . A maximum likelihood ratio information retrieval model . In Proceedings of the 8th Text REtrieval Conference . Gaithersburg, MD.

Robertson , S. E., S. Walker , S. Jones , M. M. Hancock-Beaulieu , and M. Gatford , 1994 . Okapi at TREC-3 . In Proceedings of the 3rd Text REtrieval Conference . Gaithersburg, MD.

Sparck Jones , Karen and Peter Willett (eds.) , 1997 . Readings in Information Retrieval. San Francisco, CA: Morgan Kaufmann.

Witten , Ian H . and Timothy C. Bell , 1991 . The zero-frequency problem: Estimating the probabilities of novel events in adaptive text compression . IEEE Trans. Inform. Theory, IT37 (4): 1085 - 1094 .