Thomson Legal and Regulatory participated in the CLEF-2004 monolingual and bilingual tracks. Monolingual experiments included Portuguese, Russian and Finnish. We investigated a new query structure to handle Finnish compounds. Our main focus was bilingual search from German to French. Our approach used query translation and post-translation pseudo-relevance feedback. We compared two translation models for query translation, and captured compound translations through fertility probabilities. While the fertility-based approach picks good terms, it does not help improve bilingual retrieval. Pseudo-relevance feedback, on the other hand, resulted in improved average precision.
610 Opperman Drive
2.1
The WIN system is a full-text natural language search engine, and corresponds to TLR/West Group’s implementation of the inference network retrieval model. While based on the same retrieval model as the INQUERY system [CCB92], WIN has evolved separately and focused on the retrieval of legal material in large collections in a commercial environment that supports both Boolean and natural language searches [Tur94].
Indexing Indexing of European languages considers tokens (words) as indexing units. Tokens are identified by localized tokenization rules (e.g. detecting apostrophes in French). Tokens are also stemmed using a morphological stemmer1 which also identifies compounds and their parts for compound-rich languages such as Finnish or German.
WIN does not apply a stopword list during indexing, but it does when searches are performed. As a result, all terms are indexed, although it is possible to omit some terms in document length statistics.
Document retrieval Document retrieval in WIN can be decomposed into two components: query formulation and document scoring. Query formulation identifies query concepts, while scoring find matches for such concepts in documents.
Query formulation identifies “concepts” in natural language text, and imposes a Bayesian belief structure on these concepts. In many cases, each term in the natural language text represents a concept, and a flat structure gives the same weight to all concepts. However, phrases, compounds or misspellings can introduce more complex concepts, using operators such as “natural phrase,” “compound,” or “synonym.”
We used a standard tf-idf scheme for computing term beliefs in all our runs. The belief of a single concept is given by:
belterm(Q) = 0.4 + 0.6 ∗ tfnorm ∗ idfnorm where tfnorm =
log(tf + 0.5) log(tfmax + 1.0) and idfnorm = log(C + 0.5) − log(df ) log(C + 1.0) and tf is the number of occurrences of the term within the document, tfmax is the maximum number of occurrences of any term within the document, df is the number of documents containing the term and C the total number of documents in the collection. tfmax is a weak approximation for document length.
The final document score is an average of the document score as a whole and the score of the best portion, where the best portion is dynamically computed based on query concept occurrences. 2.2
Past research has reported on the benefits of pseudo-relevance feedback. For example, the relevance feedback incorporated in OKAPI BM-25 model has been successful at CLEF (cf. [Sav01]). Recently, alternative approaches to selecting relevant documents have been introduced; for example, Sakai and Sparck-Jones [SSJ01] investigated using document summaries to support pseudorelevance feedback.
Our approach to pseudo-relevance feedback follows the work outlined by Haines and Croft [HC93] where feedback was added to Inquery.
Term selection
sw = β
X(tfnorm ∗ idfnorm) − |R| d∈R γ
X(tfnorm ∗ idfnorm) |R| d∈R (1) 1We are using the stemmer commercialized by Inxight within the LinguistX platform. where R is the set of documents considered relevant, R the set of documents considered not relevant, and |X| denotes the cardinality of set X. tfnorm and idfnorm are defined in the previous section. The β and γ weights are set experimentally.
We select terms for expansion solely on the basis of documents. We do not favor terms that appear in the original query during term selection. The sets of documents R and R are extracted from the document list returned by the original search: R correspond to the top n documents, and R to the bottom m, where n and m are determined through experiments on training data. Reformulated query We append N selected terms to the query, eliminating any terms already present in the original query. In addition, each added term is weighted by the tfnorm part of the selection weight. Weights of original query terms remain unchanged. 3
Our approach to bilingual search relies on word-by-word query translation using bilingual lexicons. We build our lexicons from parallel corpora using a statistical machine translation toolkit. In particular, we investigate how parameters from the translation models can be leveraged for selecting translations for German compounds. 3.1
In a cross-lingual search system, user queries and documents may not share the same language. Before matching between documents and queries can happen, some level of translation is required. Conventional approaches separate the translation and retrieval processes, with translation occurring prior to retrieval. However, recent efforts use language modeling [KNS03] to integrate translation and retrieval in a unified model.
We focused on query translation [HG96], rather than document translation [OH97] or the translation of both queries and documents [BRS01]. Query translation can be performed using machine translation tools [Sav01] such as Systran, machine readable dictionaries [HG96], and bilingual lexicons learned from parallel or comparable corpora. Such bilingual lexicons include similarity thesauri [SBS97] which capture the notion of translation and related terms at once; and probability tables from statistical machine translation (e.g. the table constructed by IBM Model 1) which attempt to encode exact translations only.
With queries being translated term-by-term using bilingual lexicons, a term may have multiple possible translations. By taking advantage of query structures available in INQUERY, Pirkola [Pir98] has shown that grouping translations for a given term is a better technique than allowing all translations to contribute equally. 3.2
In previous CLEF campaigns, we constructed similarity thesauri from comparable corpora, and used the thesauri to translate queries concept-by-concept. Such an approach worked fairly well, and we obtained promising results on French-English and Spanish-English retrieval. This year, we used the statistical machine translation toolkit GIZA++ [ON00] to build bilingual lexicons. Future work will include comparing both translation approaches for term-by-term query translation. Translation models 1 and 3 [BDPDPM93] introduced five models of increasing complexity. We chose to compare Model 1 and Model 3. Model 1 is intended to capture individual word translations, while Model 3 introduces modeling of local alignments and fertilities. We were particularly interested in the notion of fertility, which allows a source term to translate to zero or more target terms. In the case of German to French translations, we hoped that fertilities would capture translating German compounds into French phrases.
Using translation and fertility probabilities Using the GIZA++ toolkit, we trained models 1 and 3 on the Europarl corpus [Koe02]. We did not use the decoding phase typically associated with statistical machine translation. We simply used the translation and fertility probabilities generated by GIZA++ for each source term d and target term f : • t1(f |d), model 1 translation probabilities for model 1, • t3(f |d), model 3 translation probabilities for model 3, • n(φ|d) where φ = 0 . . . 9, fertility probabilities for model 3, and • p0, the fertility probability for the empty notion.
We subsequently defined two translation methods: a word-based method and a fertility-based method.
The word-based method lex selects the n most probable translations of each source term d using the translation probabilities. To limit adding spurious translations, we threshold translation probilities to a fixed value pmin. Consequently, the lex method may select 0 to n translations for a given term.
The fertility-based approach fert represents our attempt at capturing the translation of German compounds. With this approach, we select one translation per source term, but each translation may include multiple terms. The fert model generates for each source term d a translation set of the m most probable target terms f1, . . . , fm, ranked according to their translation probabilities t3(fi|d). The number of selected terms m is given by
ArgMax n n(φ|d) ∗ p0 φ n(φ|d) ∗ Piφ=1 t3(fi|d) if φ = 0 if φ > 0
Examples of selected translations are reported in Table 1. The first three examples capture the adequate translation for the German term. The last example, “Lawinenunglu¨cken,” is only partially translated to “avalanches” (the disaster aspect is missing). In addition, the fert method selects far too many terms because the mass of translation probabilities outweighs the fertility factor.
Additional processing of non-translated terms We performed some additional processing for non-translated terms, i.e. terms with no entry in the bilingual lexicons. In particular, we focused on compounds that did not appear in the parallel corpus.
When no translation was found for a German term, we first stemmed the German term. If translations were found for the stemmed term, we associated these translations to the original term. If still no translation was found and the stemmed term was identified as a compound, we applied the translation process to each stemmed part. The original term was associated with the translations of the compound parts. Finally, when no translation was found, the original German term was kept as the translation. Examples of compounds translated via this additional processing are given in Table 2.
Query formulation We followed [Pir98] and others in structuring translated queries to give the same importance to each original term, regardless of the number of translations. We grouped multiple translations under a weighted #SUM node. The weight associated with each translation is its translation probability.
We also investigated using a proximity operator when translating compound terms. When the original German term was a compound, we grouped all translations under the #NPHR operator2.
2The WIN #NPHR operator corresponds to Inquery phrase operator, and includes partial credit. Partial credit enables both the operator and its children to contribute to document belief scores.
Term: globale f globale mondiale global mondial chelle n(φ|d) 0.746871 0.165741 0.0617001 0.0207158 . . .
Fertility runs Our attempt to capture the translation of compounds using fertilities had limited success. We find the fert method promising inasmuch as it is able to identify adequate compound translations but suffers from selecting a single, possibly multi-term translation. The difference between runs lex and fert using Model 3 (cf. Table 3) is statistically significant3. We have already seen (“Lawinenungglu¨cken”) that the fert approach may select too many terms when the probability mass of the candidate set outweighs the fertility probability factor. In addition, selecting a single translation as does the fert approach, limits the effectiveness of retrieval. We evaluated the lex approach selecting a single translation (n = 1), and the average precision dropped to 0.26414. This result confirms our suspicion that the fert approach is hindered by selecting a single, possibly multi-term translation.
Translated compounds as phrases Next we studied the impact of query formulation with the fert approach. The fert approach captures the translation of German compounds into multiple French terms. We expected that introducing the #NPHR operator would positively impact retrieval, since French phrases were a better representation of German compounds. The results reported in Table 4 did not support our intuition: the #NPHR operator did not improve average precision. We think that partial credit diluted results, because with partial credit the children of a phrase contribute independently as concepts to document scores. In future work, we will explore alternative scoring approaches for the phrase proximity to retain the translations of a source term as a single concept.
Seeding translation models We also investigated seeding the translation models with a machinereadable dictionary. We tested only with Model 3 and found no differences between the two translation probability tables.
3We used the Wilcoxon signed-rank test, with α = 0.05. 4This difference is also found statistically significant. t1, lex, nd, NoPRF t1, lex, nd, γ = 4 (tlrde2fr4) t3, lex, nd, NoPRF (tlrde2fr2) t3, lex, nd, γ = 1 (tlrde2fr3) t3, fert, d (tlrde2fr1) t3, fert, d, γ = 1
Runs using pseudo-relevance feedback Finally we report on experiments using post-translation pseudo-relevance feedback (PRF). After the initial retrieval, we selected the five highest-ranked documents as relevant documents. We also selected the twenty lowest-ranked documents as nonrelevant. We use the non-relevant documents as a filter to prevent common words from being selected by PRF.
As can be observed in Table 5, the introduction of PRF was beneficial. We observed the typical behavior when comparing base runs and PRF. In the best case (run “t3, lex”), PRF helps improve the performance of 59% of queries and degrade 38% of the queries. In the two other runs, PRF is helpful for 50% of queries, and not so helpful for 44% of queries.
A point of interest is the comparison to the median. There is a significant difference in average precision between the base run and the PRF run using lex and Model 3; however each run compares similarly to the median of all runs. After analysis, we observed the well-documented seesaw effect of pseudo-relevance feedback: 10 queries fell below the median when PRF was added, while 8 queries rose above the median. 4
We participated in the monolingual track with three new languages: Finnish, Portuguese and Russian. We revisited our approach to compound handling and experimented with the creation of stopword lists. 4.1
Prior research During past CLEF campaigns, the handling of compounds has received a fair amount of attention. Prior research has found that, for German, Dutch, or Finnish, breaking compounds into parts and searching on the parts was beneficial to both monolingual and crosslingual retrieval [HKP+02, Md02]. Alternatively, some researchers have focused on character n-grams as indexing units for European languages (cf. [MMP01]), limiting the reliance on compound identification. Indeed character n-grams may capture compound parts without explicitly identifying compounds.
Compounds are not like phrases At CLE
With this year’s experiments, we revisited the operator and proposed a stricter proximity #NPHR0. In order to contribute to the document belief score, parts of the compound must Run #NPHR #NPHR0 appear in a compound, not in a “phrase” environment. Partial credit is still applied. In other words, we replaced the unordered proximity of 3 with a proximity of 0. This is made possible by our indexing scheme, where compounds and their parts are indexed.
Experimental results and discussion Table 6 summarizes our experimental results with Finnish compounds. We observe a small improvement in both average precision and R-Precision, although the difference is not statistically significant.
Let us note that all documents that satisfy the #NPHR0 operator also satisfy the #NPHR operator, although their belief score may be different under each condition. For some queries, e.g. query 208, the #NPHR run ranks relevant documents higher in the list, suggesting that it finds useful proximities in addition to the exact compounds. On the other hand, for other queries, e.g. query 203, the additional proximities found in documents degrade the ranked list by pushing relevant documents further down the list. We suspect that the difference in ranking is linked to the different idf values associated with the #NPHR and #NPHR0 operators. 4.2
Two sources to identify stopwords At NTCIR-4, we built upon Savoy’s work [Sav01] and we compared using collection and query log statistics to create stopword lists. We found little differences in retrieval effectiveness.
For our CLEF experiments, we merged both approaches. We selected the most frequent terms in the collection as stopwords. We subsequently enriched that list with terms extracted from query logs. No manual review of the list was performed.
For our runs, we selected the most frequent 100 and 200 stemmed terms in collections. To those collection-based lists, we added stemmed terms that occurred in over 20% of the query logs. For each language, a query log consisted of collected CLEF queries from previous campaigns. Results and discussion In Table 7, we compare our base runs with no stopword removal (none) with removing stopwords extracted from collection statistics and query logs. Stopword lists are a useful tool to make search more effective in terms of average precision. We observe statistically significant differences in average precison for all runs.
We conclude our discussion on stopword lists by outlining the need for human review. In the Finnish stopword list, we noticed cities such as Helsinki and Tampere, as well as terms like suomi (Finland, finnish language) and suomalainen (finnish). Similarly the Portuguese list contains Lisboa, Portugal, portuguˆes, governo or ministro. While such terms are frequent in the collection, they are not truly stopwords and interfered with some queries (e.g. query 231). 5
Our bilingual experiments with IBM Model 3 are promising. Using a word by word translation, we were able to capture the translation of German compounds using translation and fertility probabilities. In the future, we will expand our work to select more than one translation per source term. In addition we will investigate alternative scoring for the #NPHR operator, where partial credit is not allowed to dilute the contribution of other concepts. Finally, we will investigate whether there is added value in using Model 4 or 5 in the context of word-by-word translation. fi, none fi, 100 (tlrfi1) fi, 200 (tlrfi2) pt, none pt, 100 (tlrpt1) pt, 200 (tlrpt2) ru, none (tlrru2) ru, 100 (tlrru1) ru, 200
We find our monolingual runs satisfactory. Our reformulated compound handling in Finnish improved was beneficial when compared to our previous approach. Compound handling may also benefit from improved partial credit. We have observed similar findings with German and Korean. Our stopword experiments confirmed well-established results about stopword removal and retrieval effectiveness. [BRS01]
M. Braschler, B. Ripplinger, and P. Sch¨auble. Experiments with the eurospider
retrieval system for
W. B. Croft, J. Callan, and J. Broglio. The INQUERY retrieval system. In Proceedings of the 3rd International Conference on Database and Expert Systems Applications, Spain, 1992.
D. Haines and W.B. Croft. Relevance feedback and inference networks. In Proceedings of the Sixteenth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 2–11, 1993.
D. Hull and G. Grefenstette. Querying across languages: a dictionary-based approach to multilingual information retrieval. In Proceedings of the 19th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 49–57, 1996.
H. Hedlund, H. Keskustalo, A. Pirkola, E. Airio, and K. J¨arvelin. Uta