This paper describes the participation of the University of Neuch^atel to the CLEF 2008 evaluation campaign. In the Persian ad hoc task, we suggest using a light su xstripping algorithm for the Farsi language and the evaluations demonstrated that such an approach performs better than a simple light stemmer, an approach ignoring the stemming stage or a language independent approach (n-gram). The use of a blind query expansion (e.g., Rocchio's model) may improve the retrieval e ectiveness. Combining di erent indexing and search strategies may further enhance the corresponding MAP. In the Intellectual Property (IP) task, we try di erent strategies to select and weight pertinent words to be extracted from a patent description in order to form an e ective query. We also evaluated di erent search models and found that probabilistic models tend to perform better than vector-space schemes.
Our participation to the CLEF 2009 evaluation campaign was motivated by our objective to design and evaluate indexing and search strategies for other languages than English (e.g., Persian ad hoc retrieval track) on the one hand, and on the other, by developing e ective domain-speci c IR (patent retrieval in the current case, also called \Intellectual Property" or CLEF-IP).
If the English language was studied since 1960, other natural languages may reveal di erent linguistic constructions having an impact on the retrieval e ectiveness. For some languages (e.g., Chinese, Japanese), word segmentation is not an easy task, while for others (e.g., German), the frequent use of di erent compound constructions to express the same object or idea may hurt the retrieval quality. The presence of numerous in ectional su xes (e.g., Hungarian, Finnish), even for names (e.g., Czech, Russian) as well as numerous derivational su xes must be taken into account for an e ective retrieval. In this context, the Persian language is member of the Indo-European family but it is written using Arabic letters. The underlying morphology is more complex than the English one but we cannot qualify it as hard compared to some languages such as Turkish or Finnish. In Persian (or Farsi) language, various su xes are used to indicate the plural, the accusative or genitive cases as well as other su xes (or pre xes) are employed to derive new words.
In the Intellectual Property ad hoc task, we face clearly a domain-speci c IR problem. Based on a large set of patent descriptions written in part in three di erent languages (English, German and French), we need to retrieve patents that are similar to a submitted one. This task could be viewed as detecting con ict between patent claims or as claim validation. In such case and contrary to other search environments, the query formulation contains a large number of terms (e.g., full patent description) and the determination and extraction of the most useful terms for an e ective search are a hard task. Due to the fact that a patent is composed of di erent parts with di erent relative importances from an IR point of view, a critical problem is to de ne the most pertinent passages to form the query. We think also that a language shift may occur between the language used in the submitted patent and the language used in other patents. For example, a patent proposal may not employ directly the term \pump" but may simply describe it to avoid direct and evident con ict with existing patents. As an additional problem, the submitted patent may concern only a subpart of a given object (e.g., injection in a pump system) and pertinent items must be related not on the general object (e.g., pump) but on the speci c targeted element.
Of course we can automatically enlarge the query by extracting related terms provided by a general or specialized thesauri, by using commercial search engines or by using given web sites (e.g., Wikipedia). Using the citation information could be a way to improve the quality of the search (and such a search strategy may also cross easily the language barriers). The presence of drawings could also be used to enhance the retrieval e ectiveness in some cases and under the assumption that an e ective image-based search function is available (which is not the case for our participation).
The rest of this paper is organized as follows. Section 2 describes the main characteristics of the test-collections while Section 3 presents brie y the various IR models used in our evaluation. The evaluation of the di erent indexing and search models with our test-collections are described and analyzed in Section 4. Section 5 reports our o cial results for both the Persian ad hoc and the CLEF-IP track. Our main ndings are regrouped in Section 6. 2 2.1
The Persian test-collection used in this year's evaluation consists of newspaper articles extracted from Hamshahri (covering years 1996 to 2002). This corpus is the same one made available during the CLEF 2008 evaluation campaign and contains 611 MB of data with exactly 166,477 documents. In mean, we can nd 202 terms per document (after stopword removal). All documents contain only <text> information without further division. The last column of the Table 1 gives basic statistics for this collection. The collection also contains 50 new topics (e.g., Topic #600 - Topic #650) having total of 4,464 relevant items, with mean of 89.28 relevant items per query (median 81.5 and standard deviation 55.63). The Topic #610 has the smallest number of relevant items (e.g., 8) while the largest number of relevant items (e.g., 266) was found for the Topic #649. 2.2
For the CLEF-IP track a data collection of more than 1 million patent documents was made available. The patents are derived from sources from the European Patent O ce (EPO) and cover English, German and French patents, with at least 100,000 documents in each language. The patent can be divided into four main parts, namely \front page" (biblio and abstract), state IP
English German French # of documents 1,943,641 1,754,471 1,754,505 # of distinct terms 401,056,191 218,276,027 92,276,265
Number of distinct indexing terms per document
Mean 204.73 111.43 47.11 Standard deviation 285.99 217.71 100.32
Median 44 9 6 Maximum 15,165 6,666 2,610 Minimum 0 0 0
Number of terms per document
Mean 1,092.48 510.79 179.33 Standard deviation 2,060.91 1,155.09 482.83
Median 78 12 6 Maximum 100,001 69,841 44,257 Minimum 0 0 0 of the art, claims (actual protection) together with drawings and embedded examples and nally citations. As addition element, we may nd search reports. Each patent is stored as XML le representing the logical structure of a patent description ( lled led between 1985 and 2000). In total we have 1,958,955 patent documents representing 13.8 GB of compressed data. The patent documents follow the \Alexandria XML" DTD1, a XML DTD for standardized patent data.
Table 1 shows collection statistics. For the IP collection, the number of documents indicates the number of patents containing at least one entry in the given language. We observe that while 99.22% of the documents contain some information in English, only 89.51% contain German information and 89.56% French information.
Among the various information available in each patent document, we decided to keep only following information: revised international patent classi cation number (tag <classificationipcr>), abstract (<abstract>), patent description (<description>), claims (<claims>) and the invention title (<invention-title>) for our experiments. Not each patent contains necessarily all of these elds and each document might be written using more than one language. We also kept the language information for each eld, in order to apply language speci c indexing strategies such as stemming, stopword removal or decomposition.
For this collection three di erent sets of topics were available, a small set containing 500 queries (denoted S bundle), a medium set (1,000 or M bundle) and a large set (10,000 or XL bundle). Each topic consist of an entire patent document stored in the same format as described previously, but not included in the corpus.
Since the the whole document could not be used as query, one of the main challenges of this task was to formulate an appropriate query out of a patent document. To generate the query we applied following procedure. For each term tj contained in the abstract, description, claim or invention title of the patent, we computed a weight w(tj ) based on Equation 1. The m terms with the highest weights are then chosen as query terms.
w(tj ) =
tfj idfj pPk(tfk idfk)2 (1) where tfj is the frequency of the term tj in the patent and idfj the inverse document frequency of tj in the document collection. For our experiments we xed m = 100. We reference to this query formulation as \Q". For some runs we added the classi cation numbers contained in the patent. In such cases, the query formulation will be referenced as \QC".
In order to analyze the retrieval e ectiveness under di erent conditions, we adopted various retrieval models for weighting the terms included in queries and documents. To be able to compare the di erent models and analyze their relative merit, we rst used a classical tf idf model. We would thus take into account the occurrence frequency of the term tj in the document Di (tfij) as well as the inverse document frequency of term tj in the collection (idfj = ln( dnfj ) with n the number of documents in the corpus and dfj the number of documents in which the term tj occurs). Furthermore we normalized each indexing weight using the cosine normalization. Additionally to this classical vector-space model, we used other models issued from both the vector-space and probabilistic model families.
We implemented the \doc=Lnu, query=ltc" (or Lnu-ltc) and \doc=Lnc, query=ltc" (Lnc-ltc)
weighting schemes proposed by Buckley et al. [
wij wQj where wij represents the weight assigned to the term tj in the document Di and wQj the weight assigned to tj in the query Q. For the Lnu-ltc model the weight assigned to the document term (\doc=Lnu") is de ned by Equation 3 while Equation 4 gives the weight assigned to the query term (\query=ltc").
Relevance assessments for this collection provide two levels of relevancy. For each topic documents considered relevant (level 1) and documents highly relevant (2) are given. If we consider both relevancy levels, we have an average of 6.22 relevant items per query, with a maximum of 56 and a minimum of 3. If however we consider only highly relevant patents, we have an average of 3.46 relevant items per query, with a maximum of 18 and a minimum of 1. All evaluations in this paper are done considering documents of level 1 and 2 as relevant. We ignore evaluation done only on the highly relevant items. 3 IR Models (2) (3) (4) (5) (6) where nti is the number of distinct indexing terms in the document Di, pivot and slope are constants, and mean tf is the mean term frequency in the document Di (values are given in Table 1).
For the \doc=Lnc, query=ltc" model, the weight for the query is calculated by Formula 4 while for the document (\doc=Lnc") it is calculated using following equation: wij =
ln(tfij + 1) qPtk2Di ((ln(tfik) + 1) idfk)2
To complete the vector-space models, we implemented several probabilistic approaches. As a
rst probabilistic approach, we implemented the Okapi model (BM25) as proposed by Robertson
et al. [
ln(tfij)+1 ln(mean tf)+1 slope) pivot + slope nti
ln(tfqj + 1) idfj qPtk2Q((ln(tfqk) + 1) idfk)2 score(Di; Q) =
X qtfj log tj2Q n
dfj dfj (k1 + 1) tfij
K + tfij with K = k1 ((1 b) + b avlidl ) where qtfj denotes the frequency of term tj in the query Q, and li the length of the document Di. Average document length is represented by avdl ((values are given in Table 1) while b and k1 are constants.
As second probabilistic approach, we implemented several models issued from the Divergence of
Randomness (DFR) paradigm as proposed by Amati et al. [
P robi2j (tfij )) As a rst model, we implemented the DFR-PL2 scheme, de ned by the following equations: (7) (8) (9) (10) (11) (12) P robi1j =
P robi2j = e j tjfnij tf nij ! tf nij tf nij + 1
n + 1 Infi1j = tf nij log2 dfj + 0:5 Infi1j = tf nij log2
n + 1 ne + 0:5 P robi2j = 1
tcj + 1 dfj (tf nij + 1) with j = tcj and tf nij = tfij log2(1 + c mean dl ) where tcj represents the number of occurrences n li of term tj in the collection. The constants c and mean dl (average document length) are xed according to the underlying collection (see Table 1).
As second model issued from the DFR framework, we implemented the DFR-InL2 model where P robi2j is de ned as in Equation 8 and Inf 1 is de ned as follows where dfj is the number of documents in which the term tj appears and tf nij de ned as before.
As third and last DFR model, we implemented the DFR-IneC2 model de ned by following equations: with ne = n (1 ( nn 1 )tcj ) and tf nij = tfij ln(1 + c melain dl ).
Finally we also used a non-parametric probabilistic model based on a statistical language
model. Both Okapi and DFR are viewed as parametric probabilistic models. In this study we
adopted a model proposed by Hiemstra [
P (DijQ) = P (Di)
Y [ j P (tj jDi) + (1 tj2Q j ) P (tj jC)] with P (tj jDi) = tfij and P (tj jC) = dlfcj with lc = Pk dfk where j is a smoothing factor, li the length of documenlti Di, and lc an estimate of the size of the corpus C. In our experiments j is constant for all indexing terms tj . 4
To measure retrieval performance of our di erent runs, we adopted MAP values computed using the TREC EVAL program. Using this tool, the MAP values are computed on the basis of 1,000 retrieved documents per query. In the following tables, the best performance under the given conditions are listed in bold.
Query T Stemmer Okapi DFR-PL2 DFR-IneC2 LM tf idf Mean % over \none" The Persian language, belonging to the Indo-Aryan language family is written using 28 Arabic letters, with additional 4 letters (À P h H ) being added to express sounds not present in classical Arabic. Su xes predominate Persian morphology. Even thought this language does not have the de nite article in the strict sense, it can be said that the relative su x ø ( é» úGAJ», the book which) . and su x è ( èQå , the son, informal writing) perform this function. The plurals in the Persian are formed by means of two su xes, namely à@' for animate (PYK, father, à@PYK, fathers) and Aë for inanimate (ÉÇ, ower, AêÊÇ, owers) nouns, while the plural of Arabic nouns in this language is formed according to Arabic grammar rules (e.g., H@'or áK'for \sound" plurals). The \light" stemmer we propose for this language removes the above mentioned su xes with addition of certain number of possessive and comparative su xes, while the second stemmer we proposed, named \plural", detects and removes only the plural su xes from Persian nouns together with any su x that might follow them.
Table 2 shows the MAP achieved by ve IR models as well as di erent indexing strategies with the short query formulation. Second column in Table 2 (marked \none") depicts the performance obtained by the word based indexing strategy without stemming, followed by the MAP achieved by our two stemmers, namely \plural" and \light". In the column marked \perstem" the results obtained using publicly available stemmer and morphological analyzer for the Persian language2 are given. This stemmer is based on numerous regular expressions in order to remove the corresponding su xes. Finally the last column of the table depicts the performance of the language independent 5-gram indexing strategy. It can be seen from this table that the best performing models for all indexing strategies are the models derived from the DFR paradigm (marked bold in the table). The best performing indexing strategy proves to be the \light" stemming approach with the exception of the tf idf IR model for which the best performance was obtained by \plural" indexing approach. In all experiments presented in this paper the stoplist3 for the Persian language containing 884 terms has been used.
Table 3 shows the MAP obtained using two di erent indexing strategies, namely \none" and \light" over ve IR models with three query formulations (short or T, medium or TD and long or TDN). It can be seen from Table 3 that augmenting the query size ameliorates the MAP over T query formulation by 8% in average for TD queries and 15% for TDN queries.
Upon inspection of obtained results, we have found that the pseudo-relevance feedback (PRF
or blind-query expansion) seemed to be a useful technique for enhancing retrieval e ectiveness for
this language. Table 4 depicts MAP obtained by using Rocchio's approach (denoted \Roc") [
Query
Stemmer
Okapi
DFR-PL2
DFR-IneC2
LM
tf idf
mean
% over T
Query
Index
IR Model/MAP
PRF Rocchio
k doc./m terms
For indexing the patent documents, we applied di erent strategies depending on the language in
order to improve retrieval e ectiveness. To eliminate very frequent terms having no impact on
sense-matching between topic and document we used a language speci c stopword list for each
language. Furthermore for each language the diacritics were replaced by their corresponding
nonaccented equivalent. We also applied a language speci c stemming strategy. For the English
language we used the S-stemmer as proposed by Harmann [
Table 5 shows the MAP achieved by the seven di erent models used on the IP collection as well as the di erent indexing strategies and query formulations. The evaluations were done using the small topic set. The last line indicates the MAP average computed for all IR models. For previous art search in the patents, we tried three di erent techniques. First we weighted search terms for each eld (abstract, description, title, ...) separately and then added the results to obtain the nal score for the given document. For example if one query term appears once in the abstract and once in the title, the term would have tf one for each eld and idf related to the corresponding eld. The weight is then calculated for each eld and added up. We reference to this strategy as \Separated Fields". Second we weighted the search terms considering the whole document, i.e., if a term t occurs once in two di erent elds it has tf of two and to compute idf we consider the whole patent document. To this strategy we reference as \Single Field". The third and last strategy consist in searching only the description of the patent (\Description"). Furthermore we applied two query formulations either taking into account classi cation numbers (\QC") or not (\Q").
We observe that for all searching strategies except if we take only into consideration the
Query
Index Model / # of queries
Okapi DFR-InL2 DFR-PL2
LM Lnc-ltc Lnu-ltc tf idf Mean
Mean Average Precision (MAP)
QC Q Separated Fields Single Field
500 500 0.0832 0.0843 0.092 0.0645 0.0909 0.0515 0.0952 0.0891 0.0839 0.0554 0.0782 0.0695 0.0566 0.0380 0.0829 0.0464 description part of the patent, the language modeling approach (LM) shows the best performance. We can also see that keeping the various elds separated (index \Separated Fields") shows slightly better performance then if we index everything together. Searching only in the the description eld of the patent, we obtain similar performances as when searching in the whole patent document.
We furthermore observe that except if searching only in the description, vector-space models are generally outperformed by probabilistic models.
5.1
Table 6 gives description and results of the four o cial runs submitted to the CLEF 2009 Persian
ad hoc track. Each run is a fusion of several single runs using di erent IR models (DFR, Okapi,
statistical language model(LM)), indexing strategies (word with and without stemming, 5-gram),
query expansion strategies (Rocchio, idf -based or none) and query formulation (T, TD and TDN).
The fusion was performed for all four runs using a Z-score operator [
Run name UniNE strat1 UniNE strat2 UniNE strat3 UniNE strat4 UniNE strat5 UniNE strat6 UniNE strat7 UniNE strat8
Query
Q Q QC Q Q QC Q Q QC Q QC QC
Index Single
Single Separated Description Separated Separated
Single Description Separated
Single Separated Separated From our past experiences in various evaluation campaigns, the results achieved this year in CLEF con rm the retrieval e ectiveness of the Divergence from Randomness probabilistic model family. In particular the DFR-PL2 or the DFR-IneC2 implementation tends to produce high MAP when facing di erent test-collection. In both tracks, we found that using our Z-score operator to combine di erent indexing and search strategies tends to improve the resulting retrieval e ectiveness.
For the Persian ad hoc task, we notice three main di erences between results achieved last year and those obtained this year. First, using very short (title-only or T) query formulation, we achieved the best results in 2008. This is the contrary this year with results based on TDN topic formulation depicting the best MAP (see Table 3). Second, unlike last year, the use of our stemmers was e ective this year (see Table 2), and particularly the \light" stemming approach. Third, applying a pseudo-relevance feedback enhance the retrieval e ectiveness of the proposed ranked list (see Table 4). For the moment, we do not have found a pertinent explanation to such di erence between the two years. However, during both evaluation campaigns we found that a word-based indexing scheme using our \light" stemmer tends to perform better than a n-gram scheme.
In the Intellectual Property task (CLEF-IP), we were not able to propose an e ective procedure to extract the most useful search terms or passages able to discriminate between the relevant and non-relevant patents. In our case, we xed an arbitrary and xed limit of 100 search terms to be extracted from the submitted patent description based on their tf idf weights. We experiment di erent indexing strategies and search models. It seems that building separate index for each eld (title, abstract, description, . . . ) and then combining the resulting ranked list may improve the MAP. This task is particularly challenging knowing that only one participating group achieved a MAP clearly higher than 0.1 demonstrating also that additional evaluation campaigns are needed in this domain-speci c task.
Acknowledgments The authors would like to also thank the CLEF-2009 organizers for their e orts in developing test-collections. This research was supported in part by the Swiss National Science Foundation under Grant #200021-113273.