Mathias Géry
email: mathias.gery@univ-st-etienne.fr

Christine Largeron
email: christine.largeron@univ-st-etienne.fr

BM25t: a BM25 extension for focused information retrieval

Keywords: Probabilistic Information Retrieval model, Structured Information Retrieval, XML, Tags, Weighting scheme, BM25

HAL is

Introduction

With the development of markup languages, most of the information available on the Internet has become very structured. This has launched the development of focused information retrieval (focused IR) which aims to provide fragments of documents rather than whole documents as in classic information retrieval. The information specifically relevant to the user's needs is then identified directly within the documents. This is useful especially when the documents are long or in the context of mobile computing (e.g. smartphones, tablets, etc.). Depending on whether the list which is returned contains passages or XML elements, we may then speak more specifically of either passage retrieval or XML retrieval (XML IR) [START_REF] Lalmas | XML Retrieval. Synthesis Lectures on Information Concepts, Retrieval, and Services[END_REF][START_REF] Lalmas | XML retrieval[END_REF]. The field of XML IR has been encouraged over the past few years through the organization of workshops and competitions such as INEX [START_REF] Baeza-Yates | Introduction to the special issue on XML retrieval[END_REF][START_REF] Carmel | XML and information retrieval: a SIGIR 2000 workshop[END_REF][START_REF] Fuhr | Overview of the INEX 2007 Ad Hoc Track[END_REF][START_REF] Kamps | Report on the SIGIR 2008 workshop on focused retrieval[END_REF][START_REF] Kamps | Overview of the INEX 2008 Ad Hoc track[END_REF][START_REF] Trotman | Report on the SIGIR 2007 workshop on focused retrieval[END_REF]. However, markup languages such as XML do not only allow a document to be broken up into elements; they can also be used to annotate the text with tags so that the structure (logical, layout, formatting, links, etc.) may be described independently from the content itself.

Hence, studies in XML IR have not only been concerned with the retrieval of more concise units of information but also with the better exploitation of these tags in order to improve the detection of relevant information.

For these purposes, two types of approach have been adopted. The first one, which is user-oriented, is concerned with the development of interfaces for the visualization and navigation within results and also query-languages such as W3QS [START_REF] Konopnicki | W3QS: A query system for the world-wide web[END_REF], XIRQL [START_REF] Fuhr | XIRQL: a query language for information retrieval in XML documents[END_REF], NEXI [START_REF] Trotman | Narrowed Extended XPath I (NEXI)[END_REF][START_REF] Trotman | NEXI, now and next[END_REF], Bricks [START_REF] Van Zwol | Bricks: The building blocks to tackle query formulation in structured document retrieval[END_REF] or BusEngine-L [START_REF] Taha | BusSEngine: a business search engine[END_REF] which take into account the structure. However, the use of such query-languages remains limited, because few users are able to formulate their needs with complex queries 1 . Most of the time, those queries are expressed with a few keywords [START_REF] Kamps | Structured queries in XML retrieval[END_REF][START_REF] Kazai | Users' perspectives on the usefulness of structure for XML information retrieval[END_REF][START_REF] O'keefe | The simplest query language that could possibly work[END_REF].

The second type of approach improves the classic models and suggests a scheme for structural weighting [START_REF] Fuller | Coherent answers for a large structured document collection[END_REF][START_REF] Lalmas | Structure weight[END_REF]. Indeed, as pointed out by Tamine-Lechani et al. or by Zhu et al. the retrieval accuracy can be improved in taking into account the structure to represent documents [START_REF] Tamine-Lechani | Evaluation of contextual information retrieval effectiveness: overview of issues and research[END_REF][START_REF] Zhu | Integrating multiple document features in language models for expert finding[END_REF]. Within such a weighting scheme, the weight assigned to a word is not only based upon its frequency within the document and within the collection, but also upon its position within the document. The tags are used to define these positions. Hence, the ranking of a document depends not only upon the existence of a term within a document but also upon the tags which mark the term. Different tags can be considered, including tags related to formatting (e.g. bold, italic, center, etc.) and logical tags that define an internal structure (e.g. title, section, paragraph, etc.).

In the XML document presented in figure 1, there are logical tags like article, p and other tags like strong, emph3, collectionlink which might emphasize the important terms.

<?xml version="1.0" encoding="UTF-8"?>
 <name id="5432">Economy of Cambodia</name> <emph3> <collectionlink href="9223.xml">Economy</collectionlink> -overview: </emph3>
 During <collectionlink href="34658.xml">1995</collectionlink>, the Cambodia government implemented firm stabilization policies under difficult circumstances. Overall, macroeconomic performance was good. Growth in 1995 was estimated at 7% because of improved agricultural production (<collectionlink href="36979.xml">rice</collectionlink> in particular). Strong growth in <collectionlink href="239038.xml">construction</collectionlink> and services continued. Inflation dropped from 26% in 1994 to only 6% in 1995. Imports increased as a result of the availability of external financing. Exports also increased, due to an increase in log exports. With regard to the budget, both the current and overall deficits were lower than originally targeted.

 After four years of solid macroeconomic performance, Cambodia's economy slowed dramatically in <collectionlink xlink:href="34601.xml">1997</collectionlink>.

 Fig. 1 Tags in XML article "Economy of Cambodia" from Wikipedia

In this article, we consider the problem of extending the probabilistic model [START_REF] Maron | On relevance, probabilistic indexing and information retrieval[END_REF][START_REF] Robertson | Relevance weighting of search terms[END_REF] that aims to estimate the relevance of a document for a given query through two probabilities: the probability of finding relevant information and the probability of finding non-relevant information. The model is extended using all kind of XML tags. We suppose that both types of tags may be used to emphasize words:

-A word is undoubtedly more important if it appears within certain sections of a document (a title, a caption to a figure, a paragraph, etc.) -In the same way, a word does not carry the same emphasis if it is marked by any kind of tags, especially if it appears in a particular font (bold, italic, etc.).

Consequently, in the model which we propose, the document structure is integrated at two levels. At the first level, the logical structure is used in order to determine the granularity of the indexing, and thereby the granularity of the elements with which the system is likely to provide to the user. Therefore, the relevance is not evaluated, as is usually the case, at the document level, but rather at the level of the XML elements. Then at the second level, the logical structure and other kinds of structures are integrated in the weighting scheme. During the learning stage, a weight is given to each tag. This weight is based upon the probability that this tag highlights either a relevant term or a non-relevant term. The underlying idea is the same as in the probabilistic model [START_REF] Robertson | Relevance weighting of search terms[END_REF] which estimates the probability that a term appears in a relevant (or non-relevant) document, from a test collection where the relevance of the documents is available. At the query stage, the probability that an element might be relevant is estimated by combining the weight of the terms that it contains with the weight of their tags.

The main contribution of this paper is the following: -A theoretical framework which explicitly takes the logical tags and other tags as found in XML documents into account, by removing the limitations on the number of tags which are considered, unlike Robertson et al. [START_REF] Robertson | Simple BM25 extension to multiple weighted fields[END_REF]. -A learning stage to estimate of the weight of each tag which measures its capacity to emphasize terms in relevant passages or in non relevant passages. As the weights may have a negative impact, this stage may also be considered as a stage where the tags are automatically selected. -The extension of the BM25 weighting function [START_REF] Jones | A probabilistic model of information retrieval: development and comparative experiments -part 1[END_REF][START_REF] Jones | A probabilistic model of information retrieval: development and comparative experiments -part 2[END_REF][START_REF] Robertson | Okapi at TREC-3[END_REF] through the integration of automatically learned tag weights. -The retrieval of elements whose granularity is better adapted, especially useful for mobile applications, unlike approaches which aim to improve the retrieval of whole documents. -An evaluation of this model upon a wide collection of documents (the INEX2 collection) This model will be described in the following section. The experiments are presented in the section 3 and the results are reported in section 4 and in section 5. A state of the art is given in section 6 before the conclusion.

A probabilistic model for the representation of structured documents

Notations

Let D be a set of structured documents. Each tag describing logical structure (article, section, p, table, etc.) defines a logical element that corresponds to a part of a document. Therefore, each logical element will be represented by a set of terms and will be indexed. These elements will be returned by the system.

On the other hand, some tags are not considered as logical tags, as for example the formatting tag . This tag does not define an element to be indexed. However, it belongs to the user to define the list of logical tags and the minimum elements size.

We note:

-E = {e 1 , ..., e j , ...e l }, the set of the logical elements available in the collection; -T = {t 1 , ..., t i , ...tn}, a term index built from E; -B = {b 1 , ..., b k , ..., bm}, the set of tags.

-B l ⊂ B, the set of logical tags; -B l , the set of all the other tags.

In the following sections, the representation of an element e j is noted x j when only the terms are considered, and m j when both terms and tags are taken into account. The term based score and the tag based score are respectively detailed in the next sections.

Example

The following example presents three documents d 0 , d 1 and d 2 . Considering a query q, we suppose that the seven underlined terms are relevant: We assume that in this example the set of logical tags B l = {article, section, p}. The document d 2 is thus indexed by five elements, as presented in figure 2: an article (tag
), a section (tag
) and three paragraphs (tag
). This example shows that the content of elements included in larger ones are indexed several times, e.g. each paragraph is indexed itself as
 element, and its content is also included in the index of both elements
 and
.

d 0

 t 1 t 2 t 3

Term based relevance score for an XML element

The relevance of an element for a given query Q depends upon the weights of the matching terms (i.e. terms of the query contained in the element). The weight of the term t i in the element x j is noted w ji .

Formally, we define X j a vector of random variables and x j = (x j1 , ..., x ji , ..., x jn ) a realization of the vector X j , with x ji = 1 (resp. 0) if terms t i appears (resp. does not appear) in element e j .

Given these notations, the term based relevance f term of x j is given by the score: As mentioned by Robertson et al. [START_REF] Robertson | Simple BM25 extension to multiple weighted fields[END_REF], this general dot-product form covers different ranking functions, for example the functions ltn and ltc implemented by SMART system [START_REF] Salton | Introduction to modern Information Retrieval[END_REF], or the well known BM25 function [START_REF] Jones | A probabilistic model of information retrieval: development and comparative experiments -part 1[END_REF][START_REF] Jones | A probabilistic model of information retrieval: development and comparative experiments -part 2[END_REF][START_REF] Robertson | Okapi at TREC-3[END_REF].

f term (x j ) = ti∈T ∩Q x ji × w ji (1)
B l = {b} |d 0 | = 7; |d 1 | = 6; |d 2 | = 5; . . . |d 2 /article[1]| = 5 |d 2 /article[1]/section[1]-= 5 |d 2 /article[1]/section[1]/p[1]| = 1 |d 2 /article[1]/section[1]/p[2]| = 2 |d 2 /article[1]/section[1]/p[3]| = 2
Preliminary experiments using ltn and ltc have led to weak results [START_REF] Géry | Integrating structure in the probabilistic model for information retrieval[END_REF], thus we will henceforth only consider BM25 [START_REF] Jones | A probabilistic model of information retrieval: development and comparative experiments -part 1[END_REF][START_REF] Jones | A probabilistic model of information retrieval: development and comparative experiments -part 2[END_REF][START_REF] Robertson | Okapi at TREC-3[END_REF]:

w ji = tf ji × (k 1 + 1) k 1 × ((1 -b) + (b * ndl)) + tf ji × log N -df i + 0.5 df i + 0.5 (2) with:
tf ji : the frequency of t i in element e j .

-N : the number of elements in the collection.

df i : the number of elements containing the term t i .

ndl: the ratio between the length of element e j and the average element length (i.e. its number of terms occurrences). k 1 and b: the classical BM25 parameters.

Parameter k 1 allows setting the frequency saturation. Parameter b allows setting the importance of ndl, i.e. the importance of length normalization.

We can note that parameters k 1 and b allow modifying the bend of the curve and in some way the non linearity of the function. As an example, when k 1 is set to 1.1, a term frequency of 10 will lead to almost the same value in the tf component of the BM25 weighting function, than a term frequency of 25. This non linearity property of weighting functions is very important for our purpose. Indeed, impact of tag weight on w ji is very different than on the tf ji . Like Robertson et al. [START_REF] Robertson | Simple BM25 extension to multiple weighted fields[END_REF], we think that the impact on the term weighting function should not break the non linearity property, and thus we have compared the pre-impact of tag weights (i.e. impact on tf ji in the TTF strategy) as well as the post-impact (i.e. impact on w ji in the CLAW strategy). These different strategies are detailed in following sections.

Tag based relevance score for an XML element

Similarly to the previous section, we define M j as a vector of random variables3 T ik in {0, 1}: M j = (T 10 , ..., T 1k , ..., T 1m , ..., T n0 , ..., T nk , .., Tnm) with T ik = 1 if term t i appears in this element marked by b k T ik = 0 if term t i does not appear marked by b k T i0 = 1 if term t i appears without being marked by a tag in B T i0 = 0 if term t i does not appear without being marked We note m j = (t 10 , ..., t 1k , ..., t 1m , ..., t n0 , ..., t nk , .., tnm) a realization of the random variable M j .

In the running example given above, we have as the term t 1 is marked by article (t 11 = 1), and p (t 13 = 1) but neither by section (t 12 = 0) nor by b (t 14 = 0). We have t 10 = 0 as the term does not appear without tag.

In this section, we adapt the model introduced by Robertson et al. [START_REF] Robertson | Relevance weighting of search terms[END_REF] in order to take into account the documents structure described previously (cf. section 2.1). To do so, we not only use terms weights w ji , but also tag weights. In an information retrieval context, we wish to estimate the relevance of an XML element e j (modelled by the vector m j ) for a given query. We thus want to estimate:

P (R|m j ):
the probability of finding relevant information (R) given an element m j and a query. P (N R|m j ): the probability of finding non relevant information (N R) given an element m j and a query.

Let f 1 (m j ) be a document-ranking function:

f 1 (m j ) = P (R|m j ) P (N R|m j )
The higher f 1 (m j ), the more relevant the information represented by m j . Using Bayes formula, we get:

f 1 (m j ) = P (m j |R) × P (R) P (m j |N R) × P (N R)
The term P (R) P (N R) being constant throughout the collection for a given query, it will not change the ranking of the documents. We therefore define f 2 (which is proportional to f 1 ) as:

f 2 (m j ) = P (m j |R) P (m j |N R)
Using the Binary Independence Model assumption, we have:

P (M j = m j |R) = t ik ∈mj P (T ik = t ik |R) (3)
= t ik ∈mj P (T ik = 1|R) t ik P (T ik = 0|R) 1-t ik
In the same way, we get:

P (M j = m j |N R) = t ik ∈mj P (T ik = 1|N R) t ik P (T ik = 0|N R) 1-t ik (4)
For sake of notation simplification, we note, for a given XML element:

p i0 = P (T i0 = 0|R):
the probability that t i does not appear without being marked, given a relevant element. p ik = P (T ik = 1|R): the probability that t i appears marked by the tag k, given a relevant element. q i0 = P (T i0 = 0|N R): the probability that t i does not appear without being marked, given a non relevant element. q ik = P (T ik = 1|N R): the probability that t i appears marked by the tag k, given a non relevant element.

Using these notations in equations 3 and 4, we get:

P (m j |R) = t ik ∈mj (p ik ) t ik × (1 -p ik ) 1-t ik , P (m j |N R) = t ik ∈mj (q ik ) t ik × (1 -q ik ) 1-t ik .
The ranking function f 2 (m j ) can then be re-written:

f 2 (m j ) = t ik ∈mj (p ik ) t ik × (1 -p ik ) 1-t ik t ik ∈mj (q ik ) t ik × (1 -q ik ) 1-t ik
The log function being monotone increasing, taking the logarithm of the ranking function will not change the ranking. This leads to the function f 3 :

f 3 (m j ) = log(f 2 (m j )) = t ik ∈mj (t ik log(p ik ) + (1 -t ik ) log(1 -p ik ) -t ik log(q ik ) -(1 -t ik ) log(1 -q ik ) = t ik ∈mj t ik × log p ik 1 -p ik -log( q ik 1 -q ik ) + t ik ∈mj log( 1 -p ik 1 -q ik )
As before, the term t ik ∈mj log( 1-p ik 1-q ik ) is constant in respect to the collection (independently from t ik ). Not considering it, will lead to the ranking function f 3 (m j ):

f tag (m j ) = t ik ∈mj /ti∈Q t ik * log p ik (1 -q ik ) q ik (1 -p ik ) (5)
Thus, in this ranking function, we obtain a weight for each term t i and each tag b k . The weight of a term t i marked by b k will be written w ′ ik :

w ′ ik = log( p ik (1 -q ik ) q ik (1 -p ik ) ) (6)
Finally, in our probabilistic model which takes the document structure into account, the relevance of an XML element m j , relative to tags, is defined through f tag (m j ):

f tag (m j ) = t ik ∈mj /ti∈Q t ik × w ′ ik (7)
This formula is similar to the classical term weighting function seen in equation 1, except that tag weights are considered instead of term weights.

In practice, we have to estimate the probabilities p ik and q ik , i ∈ {1, .., n}, k ∈ {0, .., m} in order to evaluate the element relevance. For this purpose, we propose to use a learning set LS in which element relevance for a given query is known. Given the set R (respectively NR) that contains the relevant elements (respectively non-relevant ones) a contingency table can be built for each term t i marked by b k :

k R NR LS = R ∪ N R t ik ∈ m j r ik nr ik = n ik -r ik n ik t ik / ∈ m j R -r ik N -n ik -R + r ik N -n ik Total R |N R| = N -R N
with:

r ik : the number of times term t i marked by b k is relevant in LS; i r ik : the number of relevant terms marked by b k in LS. n ik : the number of times term t i is marked by b k in LS; nr ik = n ik -r ik : the number of times term t i marked by b k is not relevant in LS; -R = ik r ik : the number of relevant terms in LS; -|N R| = N -R: the number of non-relevant terms in LS.

We can now estimate

p ik = P (t ik = 1|R) = r ik R q ik = P (t ik = 1|N R) = n ik -r ik N -R

And w ′

ik follows:

w ′ ik = log r ik R (1 -n ik -r ik N -R ) n ik -r ik N -R (1 -r ik R ) (8) = log r ik × (N -n ik -R + r ik ) (n ik -r ik ) * (R -r ik ) = log r ik × (|N R| -nr ik ) nr ik × (R -r ik )
This weighting function evaluates, for a given tag, the probability of being able to distinguish between relevant and non-relevant terms: it increases according to the tag ability to distinguish a relevant term. In practice, the learning set contains a set of queries and consequently the tag weights are evaluated with an aggregation of the contingency table over all the queries.

Considering the tag b 2 = section in our example, we obtain the following contingency table for the query q and the term t 1 :

= section R NR LS = R ∪ N R t 1,2 ∈ m j r 1,2 = 1 nr 1,2 = 1 n 1,2 = 2 t 1,2 / ∈ m j R -r 1,2 = 6 N -n 1,2 -R + r 1,2 = 10 N -n 1,2 = 16 Total R = 7 |N R| = 11 N = 18
Then, we can calculate the weight w ′ 1,2 of p related to the term t 1 as follows:

w ′ 1,2 = log 1 × (11 -1) 1 × (7 -1) = log 5 3 (9)
Our model needs a learning set, as the probabilistic model needs. Obviously, such a learning set is not always available, and it can be challenging to build. In the INEX campaign for instance, the participants use an interface to highlight the relevant passages in function of their query. In this way, a training set of queries is composed and another set of queries is proposed as a test set. Its robustness has to be studied when the documents collection changes. However, when such a learning set exists, the probabilistic model can be used, and it has shown its effectiveness.

It should be noted however, that the estimation of probabilities may comprises some smoothing when the learning set is limited in size. This has not been useful for our experiments, thanks to the estimation of one weight for each tag instead of one weight for each pair (tag, term) (as explained in the next section).

Estimation of tag weights

From a theoretical point of view, we may estimate a weight for each pair (term, tag) (cf. equation 8), in other words the capacity of a tag to reinforce a relevant term (or on the contrary, to mitigate a non-relevant term). However, we aim to create a model for tag-impact, not in relation to a particular term, but generally. Indeed, we believe that the capacity of a tag to highlight relevant terms (or on the contrary, to reduce their visibility) is intrinsic to the tag itself and is therefore not dependent on the terms. The objective then is, for instance, to evaluate whether or not a word featuring in a title is more important than a word taken from a section/paragraph, regardless of the word itself. We are therefore not interested in the weight of each pair (term-tag) but instead, in the tag-weight, regardless of the terms which it labels. Thus, we estimate a weight w ′ k for each tag b k instead of a weight for each couple (term t i , tag b k ):

w ′ k = ti∈T w ′ ik |T | (10)
2.6 Estimation of the global XML element score

Having term and tag weights, a global score can be computed for ranking the elements. We propose two strategies to integrate the tag-weights into the BM25 weighting scheme:

-CLAW4 is an a posteriori impact-strategy in the results of BM25.

-TTF5 is an early impact-strategy, integrating tag-weights into the BM25 function.

In the CLAW strategy, in order to take into account all the tags that mark one given term, we propose to combine linearly the average of their weights with the weight of the term itself. This combining function, noted f claw , is defined by:

f claw (m j ) = t ik ∈mj /ti∈Q w ji × k/t ik =1 w ′ k |{k/t ik = 1}| (11)
where w ji is the t i term's weight in document m j computed by the BM25 function (see eq.2).

Géry et al. showed that the use of the tag weights raises the recall, although the improvement is not significant [START_REF] Géry | Integrating structure in the probabilistic model for information retrieval[END_REF]. On the other hand, the BM25 is non linear, the non linearity being controlled by the term frequency saturation parameter k 1 (cf. section 2.3). For this reason the integration of tag weights at a global level (i.e. on the w ji weight) is very different than their integration into the term frequency (i.e. on tf ji ). Like Robertson et al. [START_REF] Robertson | Simple BM25 extension to multiple weighted fields[END_REF], we adopt an early strategy which consist in integrate the tag-weights directly into tf ji . In this way, we take advantage of the non-linearity of the BM25 function. The new term weight (tf ji multiplied by the average of the weights of the tags that mark the term t i ), noted ttf , will replace the regular tf in the BM25 function defined in equation 2.

ttf ji = tf ji × k/t ik =1 w ′ k |{k/t ik = 1}| (12)

Experiments

The framework for our experiments is INEX 6 , the international XML IR competition which is presented in the next section. The results obtained by our model at INEX 2008 showed the advantage of taking tags into account. These results will be presented briefly in section 4. We then conducted some more in-depth experiments to study the impact of various parameters on the behaviour of our model, for classical IR which aims to provide full articles (granularity: full articles) as well as for Focused IR which returns element (granularity: XML elements). The results of these experiments are presented in section 5.

INEX collection

For our experiments, we used the INEX Ad-Hoc 2008 collection, extracted from the English Wikipedia XML corpus [START_REF] Denoyer | The Wikipedia XML corpus[END_REF]. This collection contains a significant amount of structured XML data. It also contains relevance assessments, allowing us to evaluate the quality of Focused XML IR systems.

The corpus includes 659,388 articles from the Wikipedia encyclopaedia. The original Wiki syntax was converted into XML, using both general tags for the logical structure (e.g. article, section, paragraph, title, list, item, etc.), formatting tags (e.g. bold, italic, small, etc.) and link tags (e.g. collection-link, etc.). The documents are strongly structured as they are composed of 52 million XML elements. There is no DTD fixing the available tags. Consequently, there exist 1,244 different tags in the collection, although most of them appear in very few articles. Each XML article can be viewed as a tree containing on average 79 elements and having, on average, a depth of 6.72. Moreover, whole articles (textual content + XML structure) represent 4.5 Gb of the data whereas the textual content represents only 1.6 Gb. Thus, the structural information is twice as large as the textual information.

INEX evaluation measures

The evaluation measures are based on the precision and recall, defined by Swets [START_REF] Swets | Information retrieval systems[END_REF]. iP [x] is the precision value at recall x. The average interpolated precision (AiP) combines precision and recall, calculating the average of iP [x] on 101 recall points (x = 0.00; 0.01; 0.02; ... 0.99; 1.00). This measure provides an evaluation of the system's quality for each query. By averaging the AiP values over the set of queries, an overall measure of performance is defined [START_REF] Kamps | INEX 2007 Evaluation Measures[END_REF]. This average is called mean average interpolated precision (M AiP ).

Given that every experiment is submitted to INEX in the form of a ranked list of a maximum of 1,500 XML elements for each query, these measures, in terms of recall, are in favour of the experiments for which whole articles are retrieved (thereby providing a greater quantity of information for 1,500 documents). This is problematic in the case of Focused IR because focused answers may be penalized even though the very purpose of Focused IR is to be able to retrieve short answers (in the form of relevant elements, reduced relatively to the whole article). Taking this into account, we also calculated R[1500], the recall rate for 1,500 documents, and S[1500], the size (in MB) of the 1,500 documents which were found.

It should be noted that the main ranking of the INEX competition is based on iP [0.01] instead of the overall MAiP measure, in order to take into account the importance of precision at low recall levels. Thus, Focused IR is evaluated according to precision rather than recall.

All the results presented here, including those of INEX systems, were computed using the INEX 2008 evaluation programs: inex eval, version 1.0.

Experimental protocol

All the experiments have been carried out, based on the BM25 model [START_REF] Jones | A probabilistic model of information retrieval: development and comparative experiments -part 1[END_REF][START_REF] Jones | A probabilistic model of information retrieval: development and comparative experiments -part 2[END_REF] which has been applied either in a classical way (i.e. indexing at the article level) or in a focused way (i.e. indexing at the element level). It would be interesting to evaluate our model against some other models that consider tags, as for example BM25F or BM25E, but implementing these models is very difficult upon documents collections that use hundreds of tags, as pointed out their authors (cf. section 6). We investigate the impact of tags on both levels: article and element.

INEX 2008 runs

In the learning stage, the 2006 INEX collection, composed of 659,388 articles, 114 queries and associated relevance judgements, was firstly used as a learning set in order to estimate tag-weights w ′ k . Following this, our indexing and querying experiments were carried out on the same 659,388 articles but using the 70 new queries from the 2008 edition of the INEX Ad-Hoc. Thus, the set of queries from INEX 2006 is used as a training set to learn the tag weights while the new set of queries from INEX 2008 is used as a testing set. Therefore, even if the same collection of documents is used in both stages: when estimating tag-weights (i.e. the learning stage), and during IR experiments (i.e. testing stage), they represent in fact two distinct collections from a IR point of view, thanks to the two different sets of queries. The problem of overfitting is thus avoided.

Only the key-words in each query were used (title field for INEX queries). We did not use the fields description, narrative or castitle (structured part of the query).

We experimented our model (CLAW and TTF) on a classical IR task, where the granularity for the answers is the whole article, as well as on a Focused IR task, where the granularity of the answers is the XML element. These experiments, presented in section 4 enabled us to demonstrate the advantage of taking tags into account for Focused IR within the context of our participation in INEX 2008 [START_REF] Géry | UJM at INEX 2008: Pre-impacting of Tags Weights[END_REF].

Parameter settings

Depending on the model used, different parameters need to be set. Some of them were chosen and fixed during the experiments, and other, more important ones, were studied more exhaustively:

-Fixed parameters: weighting function (BM25 [START_REF] Jones | A probabilistic model of information retrieval: development and comparative experiments -part 1[END_REF][START_REF] Jones | A probabilistic model of information retrieval: development and comparative experiments -part 2[END_REF]), minimum length of returned elements, minimum length of terms, maximum depth of returned elements, stop words, andish mode, mandatory or banned query terms (+/-operators), set of weighted tags. -Granularity-based parameters, which are fixed on one hand for classical IR (articles), and on the other hand for focused IR (elements): a set of logical tags (i.e. the kind of element the system is able to return7 ), calculation of df . -Studied parameters: tag impact (no tags, CLAW or TTF), BM25 b and k 1 .

It should be noted that a study [START_REF] Taylor | Optimisation methods for ranking functions with multiple parameters[END_REF] on the evaluation of parameters suggests that a training corpus composed of 100 queries and their assessments is enough to estimate the 9 parameters of the BM25F model that was successfully used in the TREC competition [START_REF] Zaragoza | Microsoft cambridge at TREC 13: Web and hard track[END_REF].

As previously mentioned, all the experiments were carried out with the same stop word dictionary 8 , and with the same processing of the queries (e.g. considering query operators + (mandatory terms) and -(banned terms)).

We launched some preliminary experiments in order to estimate some important parameters. Concerning the elements, the first question we face is to define the length of the smallest element the system will be able to return. As the process of conversion from the Wikipedia to INEX corpus was automatic, some very small elements are not interesting, as they cannot contain enough information. This is the case, for example, with the XML languagelink elements. Moreover, some analyses on the 2006 and 2007 assessments (not presented here) showed that it is not necessary to consider elements smaller than 10 terms, because these small elements are either non-relevant or their father is 100% relevant (and in this case it is better to return the father, which is bigger and thus easier to index). We can note that Kamps et al. showed that the optimal value for this parameter is around 40 [START_REF] Kamps | The importance of length normalization for XML retrieval[END_REF].

Another parameter which needs to be considered, as discussed by Mass et al. [START_REF] Mass | Retrieving the most relevant XML components[END_REF], is the computation of the df : should we compute the df at an element level or should we compute an overall df (e.g. at article level) without regard to the element length? Computing df at the element level will introduce a great variance in the df , and each term may be considered several times (i.e. each time it appears in an element from the same article). On the other hand, computing the df at the document level does not allow to distinguish some elements considering also the terms distribution inside articles.

We chose to calculate the df values at article level as well as at element level, i.e. the df is different for elements and for articles. Note that Taylor et al. compute an overall df [START_REF] Taylor | Optimisation methods for ranking functions with multiple parameters[END_REF], and Mass et al. compute a df at six different levels [START_REF] Mass | Retrieving the most relevant XML components[END_REF].

Tag Selection

Another important parameter is the list of logical tags, i.e. the XML elements which will be considered by the system either at indexing time or during the query step. The system will therefore not be able to return an element that does not belong to this list. Some simple statistics about the 70 tags appearing in the relevant passages in INEX 2007 assessments helped us to select the set of 16 logical tags (B l , cf. table 3). We first removed all tags occurrences when their father is more than 80% relevant. Then, to be selected, a logical tag should fulfill the following thresholds in the relevant passages:

-Number of occurrences ≥ 5.

-Average length ≥ 25 characters.

-Average relevance ≥ 10%.

-Total relevance length ≥ 5,000 characters. Although tags h4 and strong have a high score, their impact will be very low because these tags appear only around 300 times in the corpus. A formatting tag that might have a significant impact is the tag small which appears 61,132 times. We can nevertheless notice the presence of ul, section and cadre in the top 10 tags. The tag section appears more than one million times in the corpus. Its impact will thus be very important. Actually, the logical tags have more impact on the term weights than the formatting tags.

INEX results

We will now present the results obtained by our model during the 2008 INEX competition. We submitted three experiments (Foc-1, Foc-2, Foc-3) at the "Focused" Ad-hoc task. In this task, a set of 1,500 non-overlapping XML elements had to be returned. Our first objective was to obtain an efficient baseline, then to evaluate our model for classical IR and Focused IR to study the impact of having taken tag-weights into account in the BM25 function [START_REF] Jones | A probabilistic model of information retrieval: development and comparative experiments -part 1[END_REF][START_REF] Jones | A probabilistic model of information retrieval: development and comparative experiments -part 2[END_REF].

Table 6 presents the mean of the evaluation mesures on the set of queries for these three experiments. Our runs were compared to FOERStep (Waterloo University, [START_REF] Itakura | University of Waterloo at INEX 2008: Adhoc, Book, and Link-the-Wiki tracks[END_REF]) which was the winner of the Focused task. Structure is not taken into account either in Foc-1, where whole articles were returned (granularity: articles), or in Foc-2, where it is the elements which were returned (granularity: elements). However, in Foc-3, the tag-weights are integrated into BM25 for Focused IR (granularity: elements, TTF). Only 3 runs per task can be submitted to INEX. That is the reason why it was not possible to present a run Foc-4, integrating tag-weights into BM25 (granularity: articles, TTF). Nevertheless, this method was experimented later (cf. section 5). In order to take into account the non-overlapping constraint of the "Focused" task, the list of elements returned by our system were filtered by removing all the elements that overlap with another element which is better ranked. The best results (winner's iP[0.01], our best iP[0.01], MAiP, R[1500] and S[1500]) are emphasized with a bold font. The first experiment, Foc-1, in classical IR, ranked 13 th out of 61. The second experiment Foc-2, in Focused IR, did not do as well: 37 th out of 61. The early integration of the Foc-3 tag-weights (TTF strategy), in Focused IR, gave very good results and ranked 7 th out of 61, which is better than for classical IR (Foc-1) and improves the Focused IR whose recall rates were weak (from 0.5688 to 0.6640 according to the iP [0.01] criterion).

This result tends to confirm the advantage of Focused IR (Foc-3) when compared to classical IR (Foc-1). This also show the advantage of taking structural information into account (Foc-2 vs. Foc-3). Furthermore, FOERStep produces better results with low recall rates (i.e. 0.01). However, the Foc-1 experiment gives better results with recall rates at 0.05, and Foc-1 and Foc-3 give very good results in terms of recall: M AiP at 0.2791 (resp. 0.2342) and R[1500] at 0.7897 (resp. 0.6110).

We tested whether there is a significant difference between Foc-1 and Foc-3 using a paired t-test (one tailed) at 95 %. The performance (measured by MAiP) of Foc-1 is significantly better than Foc-3 but the size of the documents returned in Foc-3 is significantly lower. Indeed, at 1,500 documents, the recall decreases to 16% between Foc-1 and Foc-3 whilst the size in MB of these documents decreases by 40%. This shows that the Focused IR eliminates a greater number of non-relevant elements. In other respects, the difference (measured by iP[0.01]) is not significant. As the size of the documents returned in Focused IR (Foc-3) is lower, these experiments confirm the interest of our model in the context of mobile applications.

We also tested whether there is a significant difference between Foc-2 and Foc-3 and concluded that the performance (measured by MAiP and iP[0.01]) of Foc-3 is better than Foc-2. Consequently, we arrived, with a different collection, at the same conclusion as Robertson et al. [START_REF] Robertson | Simple BM25 extension to multiple weighted fields[END_REF]: taking tags into account in the BM25 weighting scheme is interesting if this is done early (TTF strategy, Foc-3 run), thereby maintaining the BM25's non-linearity, rather than taking the tags into account later, directly on the final term-weights [START_REF] Géry | Integrating structure in the probabilistic model for information retrieval[END_REF]. This point was confirmed by other experiments in which the pre-impact strategy (TTF) and the post-impact strategy (CLAW) are compared. These experiments are presented in the next section.

Posterior analysis

The performances of the weighting function BM25 depend a lot on the tuning of its parameters, especially those related to the documents length normalization and to the tf saturation (b and k 1 ). Subsequently, we conducted in-depth experiments to study the impact of certain parameters on the model as exhaustively as possible and to analyse its behaviour when the parameters are finely tuned. We therefore carried out several experiments using six models: articles, articles + CLAW, articles + TTF, elements, elements + CLAW, elements + TTF. Some parameters were setted after a few initial experiments (cf. section 3.4), and two important parameters were studied more thoroughly so that we might understand their influence on focused IR and to study the stability of our model. We have used a 2D grid for the parameters b (varying from 0 to 1, with 0.1 steps) and k 1 (varying from 0.2 to 3.8 with 0.2 graduations), thus a total of 6 * 11 * 19 = 1, 254 experiments.

For these posterior analyses, a different queries set was used during the learning stage (INEX 2006) than during the IR stage (INEX 2008). There is a risk of over-fitting in these "Posterior analysis" experiments, due to the tuning of the parameters using the 2008 INEX collection, which we also used to evaluate our model. This is a well-known problem in the context of IR competitions (TREC, INEX, etc.) [START_REF] Robertson | Simple BM25 extension to multiple weighted fields[END_REF][START_REF] Taylor | Optimisation methods for ranking functions with multiple parameters[END_REF]. We believe however, just as Robertson et al. [START_REF] Robertson | Simple BM25 extension to multiple weighted fields[END_REF], that it is relevant to proceed like this. Indeed we aim to determine the potential of our model by seeking the best b and k 1 parameters, bearing in mind that, in real-life conditions, we will need to discover the values for b and k 1 using a learning collection.

Summary of the results

In table 7, the results obtained with the optimal parameter configuration according to the iP [0.01] criterion are presented, while they are presented according to the M AiP criterion in table 8. Tables 7 and8 present the mean of the evaluation measures on the set of queries.

In order to situate the quality of the runs which were studied, we must add that the R7 run would have been ranked 4 th in the 2008 INEX in terms of M AiP (the winner having achieved 0.3065) while the R6 run would have been ranked 4 th in terms of iP [0.01] (the winner having achieved 0.6897).

Figure 4 presents the recall / precision curves of the 4 experiments with the best results according to the iP [0.01] criterion (R1, R3, R4, R6 runs), excluding the CLAW runs (R2, R5) which are outperformed by TTF (R3, R6). This figure shows that the elements runs (R4 and R6) seem to be outperformed by the article runs (R1 and R3). However, this is not true at low recall rates (recall <= 0.05). This is very interesting, as these precision-oriented rates are the most important in focused IR 9 .

Fig. 4 Recall / Precision of the runs with the best results.

On the impact of b and k 1 parameters

Let us now study the influence of b and k 1 parameters on the results:

The b parameter: The role of b is to control the document length normalization (cf. equation 2). This is particularly important in focused IR as the length variation for elements is greater than that of articles, as each article is fragmented into elements 10 . The k 1 parameter: The role of k 1 is to control the term frequency saturation rate, which is very important for TTF strategy, as TTF modifies directly the tf .

The CLAW strategy does not perform well (either in the competition framework or in posterior analysis). This is due to the later integration of the tags weights. Indeed, as explained previously, in the CLAW strategy the tags are introduced directly in the final term-weights, while they are introduced early in the weighting scheme in the TTF strategy. The pre-impact (TTF-strategy) permits to maintain the non-linearity of the BM25 function and thus to provide better results. The best (b, k 1 ) values are slightly higher for MAiP ((b, k 1 ) = (0.6, 2.2)) than for iP[0.01] ((b, k 1 ) = (0.4, 1.6)). These values are not far from the classical values proposed in the literature (e.g. (0.7, 1.2): for such values, the system performs an iP [0.01] of 0.6352). The length normalization of BM25 seems to be counterproductive for optimizing recall in The k 1 (tf saturation) seems to be less important for focused IR: iP[0.01] and MAiP fluctuates slightly with k 1 . Again, the best (b, k 1 ) values are different for MAiP ((b, k 1 ) = (0.1, 2.8)) than for iP[0.01] ((b, k 1 ) = (0.3, 0.8)). As in the case of focused IR without TTF strategy, the best MAiP is reached with the minimum value of b = 0.1. The behaviour of focused IR is similar with and without TTF strategy.

Classical IR

Focused IR

Focused IR and BM25t (TTF strategy)

Related works

The relevance of a document for a given query depends generally on the weight of the words in the query. This weight itself depends upon its frequency within the document and within the collection. When compared to this model, a weighting scheme permits the structure be taking into account in assigning a weight to the tags relative to their importance. This weight is then combined with those of the terms in order to determine the relevance of a document. Thus, the relevance of a document does not only depend upon the frequency with which the terms in the query occur in the document, but it also depends upon their position within that document and these positions are defined by the tags with which they have been marked. This principle has already been widely studied in the context of classic IR [START_REF] Lalmas | Structure weight[END_REF]. The tags which are considered such as their weights, may be chosen empirically. For example in [START_REF] Rapela | Automatically combining ranking heuristics for HTML documents[END_REF], the tag title has a weight of 2 and the tag abstract is set to 1.5. One obvious limit to this approach lies in the difficulty in chosing the values for the weights.

For this reason, another way consists in learning automatically the weights assigned to the tags by using for instance genetic algorithms [START_REF] Sun | SCAI experiments on TREC-9[END_REF][START_REF] Trotman | Choosing document structure weights[END_REF] or by optimizing techniques based upon simulated annealing [START_REF] Boyan | A machine learning architecture for optimizing web search engines[END_REF]. However, if the weights are not fixed by the user, again the set of tags is chosen empirically. Moreover, in these previous works, due to the computational cost, the number of tags used is very limited. In our model, the tags as well as the weights are determined automatically.

Once the weights of the tags have been determined, they should be combined with those of the words.

When logical tags are used their weight may be integrated ad hoc. In this case, the document may be divided into as many elements as it has parts (heading, abstract, main text, etc.) defined by these tags, and each part may be processed independently. Then, a linear combination of the scores obtained for each part can be computed. However, in the case of the BM25 model [START_REF] Jones | A probabilistic model of information retrieval: development and comparative experiments -part 1[END_REF][START_REF] Jones | A probabilistic model of information retrieval: development and comparative experiments -part 2[END_REF], Robertson et al. demonstrated the advantages of duplicating the parts as many times as suggested by the weights [START_REF] Robertson | Simple BM25 extension to multiple weighted fields[END_REF]. For instance, a structured document with a title-weight equal to two becomes an unstructured document with the content of the title repeated twice. The unstructured document obtained is then processed in the usual way. The experimental evaluation carried out by Robertson et al. confirms that this approach (named BM25F weighting scheme) provides better results than a linear combination of scores computed for each part [START_REF] Robertson | Simple BM25 extension to multiple weighted fields[END_REF], the advantage being that it retains the non-linearity of the BM25 weighting scheme. However, in the studies mentioned previously, the system returns complete documents and its ability to extract parts of a document has not been evaluated. This is the aim of our work. Indeed, in this article, we propose a framework for focused XML retrieval, which becomes very important with the development of mobile applications and access.

In the context of focused IR, the weighting schemes have also been studied. Once the tag-weights have been fixed, a simple strategy that can be used in order to integrate them is based on a scalar product: the tag-weights are used as multiplying factors for the term weights within their scope. This approach was used to improve the probabilistic model [START_REF] Lu | Field-Weighted XML Retrieval Based on BM25[END_REF][START_REF] Wolff | Searching and browsing collections of structural information[END_REF] as well as the vector space model [START_REF] Wilkinson | Effective retrieval of structured documents[END_REF]. However, in these works the tag-weights were arbitrarily chosen.

Other studies aim to exploit the XML tree-representation of documents [START_REF] Kotsakis | Structured information retrieval in XML documents[END_REF][START_REF] Schlieder | Querying and ranking XML documents[END_REF][START_REF] Trotman | Choosing document structure weights[END_REF]. Each XML element, corresponding to a tree-node, is characterized by a path leading from the tree-root to this node. The structure is taken into account at the term-level by considering the path of the element it contains. With this representation, Schlieder et al. introduced an extended vector model [START_REF] Schlieder | Querying and ranking XML documents[END_REF]. They computed the inverse document frequency for a term of each type of logical document found within the collection. Their system however, requires the user to give a structured query; which is not always possible. Kotsakis associates a weight directly with each path [START_REF] Kotsakis | Structured information retrieval in XML documents[END_REF]. For example, a term located on the path journal/issue/article/title has a larger weight than a term on the path journal/ issue/article/abstract. The final weight of a term is made up of two components. The first one is computed with the classical tf.idf formula, while the second one is the weight associated with the position of the word in the tree (i.e. to the path of this node). The question of how these structural weights are computed is not discussed in [START_REF] Kotsakis | Structured information retrieval in XML documents[END_REF], whereas Trotman suggests estimating the weight of each XML node using a genetic algorithm [START_REF] Trotman | Choosing document structure weights[END_REF]. This weight is then combined with the tf in various weighting schemes. These experiments showed some improvements when using vector space model or probability model, but no significant improvement was observed upon the results provided by BM25.

On the other hand, BM25E, which was introduced by Lu et al. gave promising experimental results within a focused IR framework [START_REF] Lu | Field-Weighted XML Retrieval Based on BM25[END_REF]. It is probably the model closest to the one which we are proposing in that it assigns a score to an element by affecting an early combination of the weights given to the terms in the query and those of their tags. However, in BM25E, the tag-weights are determined empirically. Furthermore, as with the majority of approaches previously cited, very few tags are taken into consideration (generally less than 5) and their choice often requires manual handling. Also, as the authors of this model pointed out "the creation of a practical algorithm to generate values for tuning parameters at the element level is a challenging task". This article tries to provide parts of an answer to this question. Unfortunately, it was not possible to compare our model, which can handle several hundred tags, against BM25E, which is "challenging" to implement in such case as mentioned by its authors [START_REF] Lu | Field-Weighted XML Retrieval Based on BM25[END_REF].

Conclusion and perspectives

In this article, we have presented a new approach for taking into account the XML structure for focused IR. This approach is inspired by probabilistic models of IR. For this purpose we propose to look at both the logical structure and all the other structures. Logical structure is used during the indexing stage in order to define the type of elements which are indexed and potentially returned by the system. The logical structure and the other structures are then integrated into the document model. During the learning stage, a weight is calculated for each tag, based upon the probability that the tags will be able to distinguish between relevant and non-relevant terms. During the query stage, calculating the relevance of an XML element for a query combines the textual content (terms) with the structure (tags which label terms).

The main contribution of this paper is a modelling of the tags ability to highlight terms according to the principles of the probabilistic IR model. Thus, the tag weights are automatically adjusted. Because the late integration of tag weights into the term weighting function only showed a slight improvement in the results (CLAW strategy), we proposed an early integration (TTF strategy) which presents the advantage to maintain the non-linearity of the BM25 function and produces much better results.

The second contribution of this work is an extensive experimentation of the BM25 model [START_REF] Jones | A probabilistic model of information retrieval: development and comparative experiments -part 1[END_REF][START_REF] Jones | A probabilistic model of information retrieval: development and comparative experiments -part 2[END_REF] in the context of XML retrieval. We evaluated our model through participation in the INEX competition. Our first experiment in classical IR (Foc-1 corresponding to a granularity of articles) came 13 th out of 61. Our second experiment (Foc-2 corresponding to a granularity of XML elements) achieved a lower ranking: 37 th out of 61. The early integration of tags in the model for focused IR (Foc-3) achieved very good results, very close to those of the best INEX systems, thereby demonstrating the advantages of focused IR (Foc-3) when compared with classical IR (Foc-1), or with structural information retrieval (Foc-2). We think that it could be possible to improve Foc-3 results in order to reach those of the best INEX systems, for example by using some query processing heuristics as some of INEX systems do.

Even if the collections which were used are very different, we have reached the same conclusions as Robertson et al. [START_REF] Robertson | Simple BM25 extension to multiple weighted fields[END_REF]: it is worthwhile taking the tags in the BM25 weighting function [START_REF] Jones | A probabilistic model of information retrieval: development and comparative experiments -part 1[END_REF][START_REF] Jones | A probabilistic model of information retrieval: development and comparative experiments -part 2[END_REF] into account, if this is done early on. But, in the context of XML retrieval, the number of tags is very large. So it is not possible to optimize dedicated parameters b and k 1 for each tag, as is done by BM25f [START_REF] Robertson | Simple BM25 extension to multiple weighted fields[END_REF] for each field. Nevertheless, we hypothesize that the tag weights used by TTF strategy can also somehow replace this fine-tuning: indeed, tag weights have an influence on the tf ji just like the k 1 parameter.

The last contribution of this article is a quite exhaustive study of the influence of the BM25's parameters b and k 1 on the iP [0.01] measure and on the M AiP . The first result provided by this study is the smooth variation of the model quality with respect to parameter changes. This is important as it shows that few experiments are useful to set up the model parameters correctly. Moreover, we can expect good behaviour in generalization. This explains the good results obtained by the system during the INEX competition. The tuning of the system done on a collection leads to good parameters to analyse a new set of queries. With the M AiP as the evaluation measure, the best model is the classical BM25 model. This can probably be explained by the fact that the measures based on recall favour systems which return large elements (granularity article). Finally, the best performances observed at low recall points, are achieved by the tag-enriched model BM25t which returns elements.

Several perspectives remain open. First of all, the TTF strategy implements a simple average of the tag-weights. Previous experiments, which are not reported in this article, showed that this method achieves better results than other functions (multiplication of weights, taking only the closest tag into account, etc.). This point should be analyzed theoretically. The average used in these experiments places all of the tags attached to a given term on the same level. A non-uniform weighting of tag-weights, for instance, according to the distance between the term and the tag, may prove more efficient.

From the experimental point of view, we focused our attention on parameters b and k 1 of the BM25 model. Other parameters also need to be studied. In particular, the way the df is computed may have great importance. Further, work is still needed in order to properly take into account the great variation of documents length in the context of focused IR. This can be done either by considering some normalization procedures as done in [START_REF] Kamps | The importance of length normalization for XML retrieval[END_REF], or by a better computation of the parameter df .

Our model has been evaluated using the INEX 2008 collection (cf. section 4), and a posterior analysis is presented but with an overfitting risk. Our model should be evaluated on other collections. The INEX collection, composed by Wikipedia XML documents, is strongly structured. We hope that our model could perform well on any collection of structured documents, as for example the INEX 2010 collection, using the INEX 2009 set of queries as a training collection. This collection is also strongly structured, even more than the INEX 2008 collection, indeed a new kind of structure is introduced by the use of semantic tags. We also hope that our model could perform well on any Web collection, as for example the TREC Web collection, composed by HTML documents.

Fig. 2

 2 Fig. 2 Modelling documents d 0 , d 1 and d 2

Fig. 3

 3 Fig. 3 Tags frequencies (top 100)

Figure 5

 5 Figure 5 presents the values of MAiP and iP [0.01] according to b on the left (resp. k 1 , on the right) in the context of classical IR. The iP [0.01] and M AiP measures presented for b (resp. k 1 ) are the ones obtained using the optimal value for k 1 (resp. b).

Fig. 5

 5 Fig. 5 Classical IR according to b and k 1

Figure 6

 6 Figure 6 presents the behaviour of the BM25 model in focused IR. The best (b, k 1 ) values are quite different for MAiP ((b, k 1 ) = (0.1, 2.2)) than for iP[0.01] ((b, k 1 ) = (0.5, 0.8)). The best MAiP is reached with the minimum value b = 0.1.The length normalization of BM25 seems to be counterproductive for optimizing recall in

Fig. 6

 6 Fig. 6 Focused IR according to b and k 1

Figure 7

 7 Figure 7 presents the behaviour of the BM25t model (TTF strategy) in focused IR.

Fig. 7

 7 Fig. 7 Focused IR + TTF according to b and k 1

  T = {t 1 , t 2 , t 3 , t 4 , t 5 }

	E = {d0/article[1], d0/article[1]/p[1], d0/article[1]/section[1],
	d0/article[1]/section[1]/p[1], d0/article[1]/section[1]/p[2],
	d1/article[1], d1/article[1]/section[1], d1/article[1]/section[1]/p[1],
	d1/article[1]/section[1]/p[2], d1/article[1]/p[1],
	d2/article[1], d2/article[1]/section[1], d2/article[1]/section[1]/p[1],
	d2/article[1]/section[1]/p[1]/b[1], d1/article[1]/section[1]/p[2],
	d2/article[1]/section[1]/p[3]}
	B = {article, section, p, b}
	B l = {article, section, p}

  b 1 = article, b 2 = section, b 3 = p, b 4 = b and T = {t 1 ,..,t 5 }.The element: e j =
 t 1 t 2 t 3
 of d 0 can be represented by the vector:m 1 = {t 10 ,t 11 , t 12 , t 13 , t 14 , t 20 , t 21 , ..., t 53 , t 54 }

	= {0, 1, 0, 1, 0, 0, 1, ..., 0, 0}

Table 1

 1 Contingency table for the term t i and for the tag b

Table 2

 2 Example: contingency table for the term t 1 and for the tag b 2

Table 3

 3 Set of logical tags B l B l = {article, cadre, indentation1, item, li, normallist, numberlist, p, row, section, table, td, template, title, th, tr} This set of tags is more or less the same for each INEX participant. The 59 tags used in the weighting function are those whose occurrences exceed 300, chosen amongst 1,244 different tags appearing in the 659,388 documents (cf. table 4). This is

Table 5

 5 Weight w ′ k of the 10 strongest and 10 weakest tags

	#	Weight w ′ k of the 6 strongest Tag Weight	Weight w ′ k of the 6 weakest tags #occs # Tag Weight #occs
	1	h4	12.32		307 45 u	0.24	3,527
	2	ul	2.70		3,050 46 i	0.23	17,935
	3	sub	2.38		54,922 47 code	0.15	5,955
	4	indentation1	2.04	135,420 48 span	0.15	2,592
	5	section	2.01	1,610,183 49 tt	0.14	6,841
	6	blockquote	1.98		4,830 50 b	0.13	11,297
	7	strong	1.97		351 51 em	0.11	608
	8	small	1.97		61,132 52 big	0.08	3,213
	9	cadre	1.91	149,002 63 font	0.07	27,117
	10 indentation2	1.82		14,065 54 emph4	0.06	940

Table 6

 6 Evaluation of 61 "Focused" task experiments

	Run	Granularity Tags	iP [0.01]	Rang M AiP	Rang R[1500] S[1500]
	FOERStep	Element	-	0.6897	1	0.2071	27	0.4494	1.11
	Foc-1	Article	-	0.6412	13	0.2791	6	0.7897	5.57
	Foc-2	Element	-	0.5688	37	0.1206	45	0.2775	0.73
	Foc-3	Element	TTF	0.6640	7	0.2342	19	0.6110	3.34

Table 7

 7 Evaluation of 1,254 runs with the iP [0.01] criterion

	Run Granularity	Tags	b	k 1	iP [0.01]	#doc	#art	R[1500] S[1500]
	R1	Articles	-	0.4	1.6 0.6587	1,457 1,457 0.8422	8.22 MB
	R2	Articles	CLAW 1.0	3.8 0.6278	1,457 1,457 0.7424	4.26 MB
	R3	Articles	TTF	0.6	1.6 0.6654	1,457 1,457 0.8214	7.69 MB
	R4	Elements	-	0.5	0.8 0.6738	1,463 1,257 0.4134	1.65 MB
	R5	Elements	CLAW 0.2	3	0.6061	1,461 1,280 0.5730	2.83 MB
	R6	Elements	TTF	0.3	0.8 0.6837	1,461 1,294 0.5180	2.98 MB

Table 8

 8 Evaluation of 1,254 runs with the M AiP criterion

	Run Granularity	Tags	b	k 1	M AiP	#doc	#art	R[1500] S[1500]
	R7	Articles	-	0.6	2.2 0.2910	1,457 1,457 0.8216	6.15 MB
	R8	Articles	CLAW 0.8	2.4 0.2522	1,457 1,457 0.8004	6.24 MB
	R9	Articles	TTF	0.6	2.6 0.2860	1,457 1,457 0.8299	7.09 MB
	R10 Elements	-	0.1	2.2 0.2664	1,459 1,408 0.7476	5.24 MB
	R11 Elements	CLAW 0.1	3.8 0.2137	1,459 1,356 0.6985	5.00 MB
	R12 Elements	TTF	0.1	2.8 0.2576	1,459 1,389 0.7285	5.37 MB

Example: "I am looking for a paragraph about running, taken from an article about marathons containing a photograph of a marathon runner."

INitiative for Evaluation of XML Retrieval. See http://www.inex.otago.ac.nz

M for Mark up. Random variables M j and its realizations m j represent structured elements.

f claw : Combining Linearly Average tag-Weights.

TTF: Tagged Term Frequency.

INEX: Initiative for the Evaluation of XML Retrieval

The set of logical tags is reduced to only one tag, i.e. article, in the case of classical IR.

Stop words list: 319 words from Glasgow Information Retrieval Group, cf. http://ir.dcs.gla.ac.uk/resources/linguistic utils/stop words

The the main INEX 2008 measure is iP [0.01]

In our experiments, we set the minimum element length at 10 words and the largest article contains 35,000 words

Acknowledgements

The authors would like to thank Franck Thollard who greatly contributed to this work. The work was supported by the Web Intelligence project (région Rhône-Alpes, cf. http:// www.web-intelligence-rhone-alpes.org).

a compromise between considering a lot of tags, which is heavy to process, and the coverage of the documents collection by these tags. Indeed, this set of tags includes all the important tags appearing in the training collection, as presented in the figure 3 showing that the tags frequencie decreases dramatically. Our set of 59 tags represents 99.99% of the 51,042,202 tags occurrencies in the collection. Only 110 tags appear more than 10 times. Afterwards, we manually removed 5 tags out of the 59: article and body because they mark the whole articles, br, s and value because they are without content. Then, the logical tags are firstly used during the indexing step to define the elements which may be returned by the system. They are secondly considered during the query step as weighting tags which impact the weight of terms. For this reason, they are marked in the third and in the fourth column in table 4, while the other tags are considered only as weighting tags and are only marked in the fourth column.

Tag Weighting

The weights of the 54 remaining tags, including 14 on 16 logical tags (as said before, article and body where removed), were computed according to equation 10. Table 5 presents


Pierre Viland
email: pierre.viland@insa-rennes.fr

Gheorghe Zaharia

Jean-François Hélard

New Efficient Method to Generate Optimal 2 n -PSK STTCs with a Large Number of Transmit Antennas

In this paper, we propose a new method called coset partitioning to generate easily and efficiently the best space-time trellis codes (STTCs), thereby reducing considerably the usual important search time. This method, used in the case of 2 n -PSK STTCs, is an extension of the set partitioning proposed by Ungerboeck based on the coset and lattice Calderbank's approach. The main guideline of the coset partitioning is to divide the set of MIMO symbols into cosets, not into simple sets as the set partitioning. The case of a large number of transmit antennas is considered because the time to obtain the best STTCs with an exhaustive search is very important when the number of transmit antennas increases. Using the coset partitioning, new 4-PSK STTCs with 5 to 6 transmit antennas are generated. Simulation results show that the new codes slightly outperform the best corresponding known codes. Thanks to the effectiveness of the coset partitioning, for the first time, 4-PSK STTCs with 7 and 8 transmit antennas and 8-PSK STTCs with 5 to 6 transmit antennas are obtained. Their performance is also analyzed by simulation.

Introduction

In [START_REF] Tarokh | Space-time codes for high data rate wireless communication: Performance criterion and code construction[END_REF], Tarokh et al. have introduced the concept of space-time trellis codes (STTCs) to take benefit from the detrimental effect of multipath fading on wireless communications. In order to improve the reliability and/or data rate of the wireless communications, STTCs take advantage of both the spatial diversity provided by the multiple input and output (MIMO) antennas and the coding gain provided by the trellis encoder. In [START_REF] Tarokh | Space-time codes for high data rate wireless communication: Performance criterion and code construction[END_REF], the rank and determinant criteria have been proposed to analyzed the performance of STTCs in the case of slow Rayleigh fading channels.

In [START_REF] Chen | Improved space-time trellis coded modulation scheme on slow fading channels[END_REF], Chen et al. have presented the trace criterion for slow and fast Rayleigh fading channels.

Based on the Euclidean distance, this criterion governs the performance of codes in the case of a great product between the number of transmit and receive antennas. Thanks to these criteria, after a systematic search, many codes have been proposed in [START_REF] Tarokh | Space-time codes for high data rate wireless communication: Performance criterion and code construction[END_REF][START_REF] Chen | Improved space-time trellis coded modulation scheme on slow fading channels[END_REF][START_REF] Chen | Space-time trellis codes with two, three and four transmit antennas in quasi-static flat fading channels[END_REF][START_REF] Hong | New space-time trellis codes for two-antenna quasi-static channels[END_REF], but only for MIMO systems with up to 4 transmit antennas. In [START_REF] Abdool-Rassool | Fast search techniques for obtaining space-time trellis codes for Rayleigh fading channels and its performance in CDMA systems[END_REF][START_REF] Abdool-Rassool | Search for spacetime trellis codes: novel codes for Rayleigh fading channels[END_REF], Abdool-Rassool et al. have presented 4-PSK STTCs with 5 and 6 transmit antennas obtained via a systematic search. The main problem of these previous published code searches is the computational time, particularly when the number of transmit antennas, the number of states and the modulation indices increase. For example, there are several billions of 4 states 4-PSK STTCs with 4 transmit antennas which must be analyzed to find the best STTCs.

In order to reduce drastically the search time, a new method called coset partitioning is presented to generate 2 n -PSK STTCs with a large number of transmit antennas without the usual time-consuming exhaustive/systematic search. In [START_REF] Viland | Design of the best space-time trellis codes based on coset partitioning[END_REF], the coset partitioning has been used to design optimal 2 n -PSK STTCs, but only for a small number of transmit antennas. This method is an extension for MIMO systems of the set partitioning proposed by Ungerboeck to design trellis coded modulations (TCMs) [START_REF] Ungerboeck | Channel coding with multilevel/phase signals[END_REF][START_REF]Trellis-coded modulation with redundant signal sets part I: Introduction[END_REF][START_REF]Trellis-coded modulation with redundant signal sets part II: State of the art[END_REF], based on the lattice and coset Calderbank's approach [START_REF] Calderbank | New trellis codes based on lattices and cosets[END_REF].

In the coset partitioning, the MIMO symbols are regrouped into cosets, not into simple sets, as in the set partitioning. Thus, the number of codes generated by the coset partitioning is reduced compared to the number of codes obtained with the set partitioning. Therefore, the time to find optimal STTCs via the coset partitioning is considerably shortened, especially when the number of transmit antennas and/or the number of states increase.

The paper is organized as follows. Section II describes the representation of STTCs and the existing design criteria. In section III, the new method is presented with several design examples.

Section IV gives new 4-PSK and 8-PSK STTCs with 5 to 8 and with 5 to 6 transmit antennas respectively. In section V, the performance of these new codes is compared to that of the best known codes.

2 System model and design criteria

Representation of a space-time trellis encoder

We consider a 2 n -PSK space-time trellis encoder with n T transmit antennas and n R receive antennas. For n = 2, the encoder is shown in Fig. 1.

The encoder is composed of one input block of n bits and ν memory blocks of n bits. A state is defined by the binary values of the ν memory blocks. At each time t ∈ Z, all the bits of a block are replaced by the n bits of the previous block. For each block i with 1

≤ i ≤ ν + 1, the j th bit with 1 ≤ j ≤ n is associated to n T coefficients g k j,i ∈ Z 2 n , 1 ≤ k ≤ n T . With these n T × n(ν + 1)
coefficients, a generator matrix G G G with n T lines and ν + 1 blocks [START_REF] Baro | Improved codes for space-time trellis-coded modulation[END_REF] is obtained :

G G G = [G 1 1 • • • G 1 n | • • • |G ν+1 1 • • • G ν+1 n ] (1)
with

G i j = [g 1 j,i • • • g n T j,i ] T ∈ Z n T 2 n . The matrix [• • • ] T is the transpose of the matrix [• • • ].
At each time t, the encoder output y y y

x t = y t 1 y t 2 • • • y t n T T ∈ Z n T 2 n is given by y y y x t = G G Gx x x t (2)
where

x x x t = [x t 1 • • • x t n • • • x t-ν 1 • • • x t-ν n ]
T is the extended-state at time t of the L = n(ν + 1) length shift register realized by the input block followed by the ν memory blocks.

Each encoder output y t k is mapped onto a 2 n -PSK signal s t k = exp(j π 2 n-1 y t k ). Each output signal s t k is sent to the k th transmit antenna. At each time t, the symbols transmitted simultaneously over the fading MIMO channel are given by s s s

t = s t 1 s t 2 • • • s t n T
T .

An encoder can also be represented by a trellis, as shown in Fig. 2 for a 4 states 4-PSK STTC.

In the trellis, the states are described by the points and the transitions between the states by the lines. Each transition corresponds to an extended-state.

Design criteria

The main design criteria have been established in [START_REF] Tarokh | Space-time codes for high data rate wireless communication: Performance criterion and code construction[END_REF][START_REF] Chen | Improved space-time trellis coded modulation scheme on slow fading channels[END_REF] in order to decrease the bit and frame error rates. In this paper, only the case of slow fading channels is considered, i.e. the channel fading coefficients are constant for each frame of L f symbols. Besides, we assume that a maximum likelihood algorithm is used to estimate the transmitted symbols.

The main goal of this design is to reduce the pairwise error probability (PEP) which is the probability that the decoder selects an erroneous frame. It is possible to represent a coded frame of L f MIMO symbols starting at t = 0 by a n T × L f matrix S S S = [s s s 0 s s s 1 ...s s s L f -1 ], where s s s t is the t th MIMO symbol. An error occurs if the decoder decides that another frame E E E = [e e e 0 e e e 1 ...e e e L f -1 ] was transmitted. Let us define the n T × L f difference matrix B B B = E E E -S S S:

B B B =         e 0 1 -s 0 1 . . . e L f -1 1 -s L f -1 1 . . . . . . . . . e 0 n T -s 0 n T . . . e L f -1 n T -s L f -1 n T         (3)
The n T × n T product matrix A A A = B B BB B B * is introduced, where B B B * denotes the hermitian of B B B.

We define r = min(rank(A A A)), where A A A is computed for all pairs of different coded frames (E E E = S S S).

The design criteria depend on the value of the product rn R .

First case: rn R ≤ 3:

In this case, for a slow Rayleigh fading channel, two criteria have been proposed [START_REF] Tarokh | Space-time codes for high data rate wireless communication: Performance criterion and code construction[END_REF][START_REF] Liao | Improved code design criteria for space-time codes over quasi-static flat fading channels[END_REF] to reduce the PEP:

• A A A has to be a full rank matrix for any pair (E E E, S S S) with E E E = S S S.

• The coding gain is related to the inverse of η = Second case: rn R > 3:

In [START_REF] Chen | Improved space-time trellis coded modulation scheme on slow fading channels[END_REF], it is shown that for a large value of rn R , which corresponds to a large number of independent SISO channels, the PEP is minimized if the sum of all the eigenvalues of the matrix A A A is maximized.

Since A A A is a square matrix, the sum of all the eigenvalues is equal to the trace of the matrix A A A:

tr(A A A) = n T k=1 λ k = n T k=1   L f -1 t=0 e k t -s k t 2   (4)
For each pair of codewords, tr(A A A) is computed. The minimization of the PEP amounts to using a code which has the maximum value of the minimum trace computed for all different pairs of coded frames (E E E, S S S). In [START_REF] Liao | Improved code design criteria for space-time codes over quasi-static flat fading channels[END_REF], it is also stated that to minimize the frame error rate (FER), the number of error events with minimum trace has to be minimized.

In this paper, we consider the case rn R > 3 which is encountered when the minimum rank of A A A is greater than 1 and there are at least 2 receive antennas.

3 Coset partitioning

Preliminary

Each MIMO symbol belongs to the additive group Z n T 2 n . The set

C 0 = 2 n-1 Z n T 2 (5) is a normal subgroup of Z n T 2 n such as v = -v, ∀v ∈ C 0 . It is possible to partition the group Z n T 2 n
into 2 n T (n-1) cosets as:

Z n T 2 n = p∈Z n T 2 n-1 (p + C 0 ) = p∈Z n T 2 n-1 C p (6)
where

C p = p + C 0 , ∀p ∈ Z n T 2 n-1 .
Using the cosets C p , it is possible to make a new partition of Z n T 2 n :

Z n T 2 n = n-1 k=0 E k (7)
where E 0 = C 0 . For 1 ≤ k ≤ n -1, the other sets E k are defined by :

E k = p k (p k + C 0 ) (8)
where

p k ∈ 2 n-k-1 Z n T 2 k \2 n-k Z n T 2 k-1 . The set Z n T 1 contains only the nul element of Z n T 2 n . For 1 ≤ k ≤ n -1, each coset p k + C 0 ⊂ E k is called 'relative to' q k = 2p k ∈ E k-1 . For example,
Table 1 shows the partition of the group Z 4 2 .

Presentation of the coset partitioning

In [START_REF] Ungerboeck | Channel coding with multilevel/phase signals[END_REF][START_REF]Trellis-coded modulation with redundant signal sets part I: Introduction[END_REF][START_REF]Trellis-coded modulation with redundant signal sets part II: State of the art[END_REF], Ungerboeck has proposed the set partitioning to design the TCMs in the case of single input and single output (SISO) systems. The set partitioning can be stated by the following rules:

Rule 1 Each point of the constellation has the same number of occurrences.

Rule 2 In the trellis, transitions originating from a same state or merging into a same state should be assigned subsets which contain signal points separated by the largest Euclidean distances.

Rule 3 Parallel paths should be assigned signal points separated by the largest Euclidean distances.

Since the trellis of STTCs has no parallel paths, this rule is not relevant for STTCs design.

Calderbank et al. give an alternative to set partitioning [START_REF] Calderbank | New trellis codes based on lattices and cosets[END_REF]: the constellation must be a subgroup of an abelian group. The subgroup is divided into cosets. At each time t, the encoder selects one coset, then one element of this coset.

The proposed method called coset partitioning can be stated by the following properties.

Property 1 The used MIMO symbols are equally probable.

Property 2

The MIMO symbols originating from or merging to a same state belong to the same coset.

Property 3 The elements of each coset must be separated by the largest Euclidean distances.

For a 2 nν states 2 n -PSK STTC, the generator matrix has ν + 1 blocks of n columns of n T lines.

A characteristic of the STTCs designed with the coset partitioning is that the

n columns of each block [G i 1 • • • G i n ] of G G G, with 1 ≤ i ≤ ν + 1 generate a subgroup Λ i of Z n T 2 n : Λ i =    n j=1 x j G i j mod 2 n /x j ∈ {0, 1}    (9) with card(Λ i ) = 2 n .
In order to obtain a subgroup, the n columns must be selected as follows. The first column

G i 1 must belong to C * 0 .
If j -1 first columns have been previous selected and create a subgroup Λ i,j-1 , the columns G i j with 2 ≤ j ≤ n and 1 ≤ i ≤ ν + 1 must belong to C * 0 or to the cosets relative to an element of Λ i,j-1 and must not belong to Λ i,j-1 .

Thus, the n columns of each block generate a subgroup. For each subgroup, it is possible to compute the minimal Euclidean distance between its elements. The sets of n columns generating the subgroups with the largest value of the minimal Euclidean distance are used to design the generator matrix G G G. After these choices, it is possible to permute the columns and the lines within each block in order to obtain other codes which fulfill the properties of the coset partitioning.

Further on, the codes with the best trace are searched.

Rule 1 of set partitioning is fulfilled by the STTCs designed via the coset partitioning because these STTCs are balanced codes [START_REF] Ngo | Balanced QPSK space-time trellis codes[END_REF][START_REF] Viland | A new method to design balanced space-time trellis codes for several transmit antennas[END_REF]. A STTC is balanced if and only if the generated MIMO symbols y y y have the same number of occurrences n(y y y) = n 0 ≥ 1 when the input data are sent by a binary memoryless source with equally probable symbols. If the columns of the generator matrix G G G generate a subgroup of Z n T 2 n , then the corresponding STTC is balanced [START_REF] Viland | A new method to design balanced space-time trellis codes for several transmit antennas[END_REF].

For a STTC designed with coset partitioning, the set

Λ = ν+1 i=1 Λ i (10)
of generated MIMO symbols is a subgroup of Z n T 2 n , where Λ i is the subgroup generated by the n columns of the block i of G G G. Thus, for these codes, rule 1 of set partitioning is respected.

If the code is designing with the coset partitioning, rule 2 of the set partitioning is also followed.

In fact, in the case of set partitioning, the symbols originating from or merging to a same state belong to a subset which contains symbols separated by the largest Euclidean distances. In the case of coset partitioning, the MIMO symbols originating from or merging to a same state belong to a coset which contains MIMO symbols separated by the largest Euclidean distances.

However, in the case of coset partitioning, the selection of 'optimal' cosets is more restrictive than the selection of 'optimal' subsets used by set partitioning. Therefore, the number of STTCs obtained via the coset partitioning is significantly reduced to the best ones.

Design examples for 4-PSK 4 states STTCs with n T transmit antennas

The MIMO symbols belong to Z n T 4 . This group can be divided into 2 subsets: E 0 = C 0 and

E 1 = (g + C 0 ), with g ∈ Z n T 2 \[0 • • • 0] T .
The generator matrix G G G has 2 blocks of 2 columns:

B i = [G i 1 , G i 2 ]
, where

G i j ∈ Z n T 4 for 1 ≤ i ≤ 2 and 1 ≤ j ≤ 2.
To design optimal STTCs, the columns of each block must generate a subgroup of

Z n T 2 n . The subgroup Λ 1 = 2 j=1
x j G 1 j mod 4/x j ∈ {0, 1} generated by the first block is also denoted Λ F 1 because it is used to generate the MIMO symbols originating From a same state, as will be shown later. The subgroup Λ 2 = 2 j=1

x j G 2 j mod 4/x j ∈ {0, 1} generated by the second block is also denoted Λ M 1 because it is used to generate the MIMO symbols Merging to a same state, as will be shown later. The set of generated MIMO symbols is given by Λ =

2 i=1 2 j=1 x i j G i j mod 4/x i j ∈ {0, 1} . Thus, each coset of Λ/Λ F 1 = g + Λ F 1 /g ∈ Λ M 1 contains
the MIMO symbols originating from a same state. In the same way, each coset of Λ/Λ M 1 =

g + Λ M 1 /g ∈ Λ F
1 contains the MIMO symbols merging to a same state. The trellis is shown in Fig. 3.

To respect the coset partitioning, the Euclidean distances between the different elements of each coset of Λ/Λ F 1 and Λ/Λ M 1 must have the largest values. To obtain these optimal cosets, it is sufficient to design the optimal subgroups. In fact, the distance spectrum of each coset of Λ/Λ F 1 and Λ/Λ M 1 , i.e. the repartition of Euclidean distances between the elements of each coset of Λ/Λ F 1 and Λ/Λ M 1 , is identical to the distance spectrum of Λ F 1 and Λ M 1 respectively. Besides,

for a 2 n -PSK modulation, d 2 E (0, v) = d 2 E (0, -v) where d 2 E (0, v) is the squared Euclidean distance
between the MIMO signals corresponding to the MIMO symbols 0 and v. As the opposite of each MIMO symbol of one block is generated, the number of constraints used to find the optimal block is reduced compared to the set partitioning.

A exhaustive search has been performed to find the best 4-PSK blocks for 5 to 8 transmit antennas whose columns generate a subgroup of Z n T 2 n . The optimal blocks are based on the permutation of the lines and/or the columns of the blocks presented in Table 2. In this table, the notation "1/3" must be read "1 or 3".

Let us consider the distance spectrum of one block of G G G. The distance spectra generated by the proposed blocks are optimal and given in Fig. 4. The best codes are constituted by 2 optimal blocks.

Design example for 16 states 4-PSK STTCs with n T transmit antennas

The MIMO symbols belong to Z n T 4 . This group can be divided into 2 sets of cosets: E 0 = C 0 and

E 1 = (g + C 0 ) with g ∈ Z n T 2 \[0...0] T . The matrix G G G has 3 blocks of 2 columns: B 1 = [G 1 1 , G 1 2 ], B 2 = [G 2 1 , G 2 2 ] and B 3 = [G 3 1 , G 3 2 ], where G i j ∈ Z n T 4 for 1 ≤ i ≤ 3 and 1 ≤ j ≤ 2. Hence, the generator matrix is G G G = [G 1 1 G 1 2 |G 2 1 G 2 2 |G 3 1 G 3 2 ].
In the case of a 16 states 4-PSK STTC designed via the coset partitioning, the trellis can be represented as shown by Fig. 5. On the left side of the trellis, there are the MIMO symbols y y y i , with 0 ≤ i ≤ 63, originating from a same state. On the right side of the trellis, there are the MIMO symbols merging into a same state.

In this case, the generator matrix is G G G = [y y y 1 y y y 2 |y y y 4 y y y 8 |y y y 16 y y y 32 ]. To design G G G, there are two steps

The first step is to select the columns of the B 1 and B 3 . The first block and the last block of the generator matrix generate respectively the subgroups Λ F 1 = {y y y 0 , y y y 1 , y y y 2 , y y y 3 = y y y 1 + y y y 2 mod 4} and Λ M 1 = {y y y 0 , y y y 16 , y y y 32 , y y y 48 = y y y 16 + y y y 32 mod 4}. Each coset of Λ/Λ F 1 and of Λ/Λ M 1 corresponds to the transitions originating from a same state and the transitions merging into a same state respectively. The selection of B 1 and B 3 is identical to the previous section. Thus, B 1 and B 3 correspond to one of the blocks proposed in the previous section after an eventual permutation of lines and/or columns.

The second step is the selection of the columns G 2 1 and G 2 2 of the second block. These columns must be selected via the previous stated properties to obtain a subgroup.

Finally, the columns of each block are permuted to obtain the codes with the best trace.

Design examples for 8-PSK 4 states STTCs with n T transmit antennas

In this case, the MIMO symbols belong to

Z n T 8 = E 0 ∪ E 1 ∪ E 2 ,where E 0 = C 0 = 4Z n T 2 , E 1 = (g 1 + C 0 ) with g 1 ∈ 2Z n T 2 \[0 • • • 0] T and E 2 = (g 2 + C 0 ) with g 2 ∈ Z n T 4 \2Z n T 2 . The generator matrix G G G is constituted by 2 blocks of 3 columns B 1 = [G 1 1 G 1 2 G 1 3 ] and B 2 = [G 2 1 G 2 2 G 2 3 ],
where

G i j ∈ Z n T 8 for 1 ≤ i ≤ 2 and 1 ≤ j ≤ 3.
Each block must generate a subgroup of Z n T 8 with 8 elements. In this case, the subgroup of MIMO symbols generated by the encoder is Λ =

2 i=1 3 j=1 x i j G i j mod 8/x i j ∈ {0, 1} . Besides, the subgroups Λ 1 = Λ F 1 = 3 j=1 x j G 1 j mod 8/x j ∈ {0, 1} and Λ 2 = Λ M 1 = 3 j=1
x j G 2 j mod 8/x j ∈ {0, 1} are generated by B 1 and B 2 respectively. The 8 MIMO symbols originating from a same state or merging into a same state are the elements of one of the 8 cosets of Λ/Λ F 1 and Λ/Λ M 1 respectively.

For 8-PSK STTCs, the optimal blocks are formed by one column of E 0 , one column of E 1 and one column of

E 2 i.e. G i 1 ∈ C 0 , G i 2 ∈ (p + C 0 ), with 2p = G i 1 and G i 3 ∈ (q + C 0 ), with 2q = G i 2 .
Remark : Some codes may have the first j columns of the (ν + 1) th block with 1 ≤ j ≤ n -1, equal to the null vector. In this case, the number of states is 2 nν-j . The columns which generate the subgroup Λ M 1 of the MIMO symbols which merge into a same state, are the first j columns of ν th block and the last (n -j) columns of the (ν + 1) th block.

Example of search time reduction

To show the usefulness of the coset partitioning, the case of 4 states 4-PSK STTCs with 3 transmit antennas is considered. To find the best codes, the minimum trace of codes must be computed.

With an exhaustive search, the number of generator matrices is egal to 4 12 = 16 777 216.

Chen et al. have proposed a suboptimal method in [START_REF] Chen | Space-time trellis codes with two, three and four transmit antennas in quasi-static flat fading channels[END_REF]. Using this method, 65 792 generator matrices are designed. This number corresponds to 0.39% of the possible generator matrices.

Rassool et al. have proposed in [START_REF] Abdool-Rassool | Search for spacetime trellis codes: novel codes for Rayleigh fading channels[END_REF] a method which ensures to obtain the optimal STTCs. The number of generator matrices is 1 398 101, i.e. 8.33% of the possible generator matrices.

With the proposed method, each block must generate a subgroup. There are 2×7×(7+8) = 210 possibilities to select 2 no null columns (including the permutations between the columns). As there are two blocks, the number of generator matrices is 210 2 = 44 100. These matrices are generated in just one second with a simple computing program. So, it is sufficient to search the best codes among these 0.26% of the possible codes. The proposed method reduces the search time and leads to better STTCs than the corresponding Chen's codes.

When the number of transmit antennas and/or the number of states increase, the percentage of codes generated by the coset partitioning decreases. For example, we consider a 4 states 4-PSK STTC with 5 transmit antennas. The number of generator matrices is 4 5×4 = 4 20 and the number of possibilities to select 2 no null columns to generate a subgroup is 2 × 31 × (31 + 32) = 3 906 (including the permutation between the columns). The generator matrices contain 2 blocks. Thus, the number of codes generated by the coset partitioning is 3 906 2 , corresponding to 0.0014% of all the possible 4 states 4-PSK STTCs with 5 transmit antennas.

New codes

New codes have been generated via the coset partitioning. Tables 3 and4 show new 4/16/32 states 4-PSK STTCs for 5 transmit antennas and 6 transmit antennas respectively and the corresponding Rassool's STTCs [START_REF] Abdool-Rassool | Fast search techniques for obtaining space-time trellis codes for Rayleigh fading channels and its performance in CDMA systems[END_REF][START_REF] Abdool-Rassool | Search for spacetime trellis codes: novel codes for Rayleigh fading channels[END_REF].

The trace of the proposed codes is equal to the trace of the corresponding Rassool's codes.

However, for the new codes, the Euclidean distances between the MIMO symbols originating from or merging to a same state are greater than the corresponding Euclidean distances of the Rassool's codes.

Table 5 shows the best 4 states 4-PSK STTCs with 7 and 8 transmit antennas. In the previous publications, no STTC has been proposed with more than 6 transmit antennas. Table 6 shows the best 8 states 8-PSK STTCs with 5 and 6 transmit antennas. In the previous publications, no 8-PSK STTC has been proposed with more than 4 transmit antennas.

Code Performance

The performance of each code is evaluated by simulation over slow Rayleigh fading channels.

The channel fading coefficients are independent samples of a complex Gaussian process with zero mean and variance 0.5 per dimension. These channel coefficients are assumed to be known by the decoder. Each frame consists of 130 4-PSK or 8-PSK MIMO symbols. For the simulation, there are 2 receive antennas. The decoding is performed by the Viterbi's algorithm.

Figs. 6 and7 show the performance of the STTCs for 5 and 6 transmit antennas presented in Tables 3 and4. Each new code outperforms slighty the best corresponding Rassool's code. The performance of the codes with 7 and 8 transmit antennas is presented in Fig. 8. The performance of the new 8-PSK codes proposed in Table 6 is shown in Fig. 9.

Conclusion

In order to decrease significantly the time to search the best STTCs, a new and simple method called coset partitioning has been presented in this paper. This method is based on a coset approach of the set partitioning used for MIMO systems. The general rule of this new method is to regroup the MIMO symbols originating from or merging to the same state into cosets, not into simple sets as the set partitioning. These cosets are obtained via a division of the generator matrix into blocks. The columns of each block must generate a subgroup of Z n T 2 n and the MIMO symbols generated by the first block and those generated by the last block must be separated by the largest Euclidean distance respectively. Thus, the number of codes which must be analyzed is considerably reduced. For example, it is sufficient to analyze 0.0014% of all the possible 4 states 4-PSK STTCs with 5 transmit antennas to find the optimal codes. To emphasize the important search time reduction, the case of STTCs with a great number of transmit antennas has been considered. New 4-PSK codes with 5 to 8 transmit antennas and new 8-PSK codes with 5 to 6 transmit antennas, obtained with the coset partitioning, have been proposed. When similar codes are available, simulation results show that the new codes slightly outperform the best previous published codes. Table 2:

n T Optimal blocks 5     0 0 2 2 2 2 2 1/3 1/3 1/3     T 6     0 0 2 2 2 0 2 2 1/3 1/3 1/3 1/3     T 7     0 0 2 2 2 2 2 2 2 1/3 1/3 1/3 1/3 1/3     T 8     0 0 2 2 2 2 2 2 2 2 1/3 1/3 1/3 1/3 1/3 1/3     T Table 3: States Code G G G Trace 4 Rassool et al.       2 3 2 0 0 2 3 2 3 2 2 3 2 3 2 1 0 2 3 2       26 New 1       2 3 1 2 0 2 3 2 0 2 2 0 2 3 2 0 2 3 1 2       26 16 Rassool et al.       2 0 1 2 2 0 1 2 3 2 1 2 3 2 2 0 1 2 2 1 0 2 2 3 1 2 2 0 3 2       40 New 2       0 2 2 3 0 2 0 2 0 2 2 3 2 1 2 3 0 2 2 1 2 3 2 3 2 1 2 1 2 1       40 32 Rassool et al.       2 1 2 3 0 3 0 1 2 3 2 0 1 0 0 2 2 2 1 2 2 1 0 0 2 0 1 2 2 3 0 0 0 2 2 3 3 2 0 2       44 New 3       0 2 2 1 2 1 0 1 0 2 2 3 0 0 0 2 2 1 2 3 2 1 0 3 2 1 2 1 2 1 0 3 2 3 0 2 2 3 0 1       44
Table 4:

States Code G G G Trace 4 Rassool et al.        0 2 1 2 1 2 2 0 0 2 1 2 2 1 2 0 1 2 2 1 2 1 2 3        32 New 4        0 2 1 2 0 2 2 0 2 1 3 2 2 1 3 2 2 3 2 0 2 3 1 2        32 16 Rassool et al.        1 2 2 0 3 2 3 2 3 2 1 2 2 0 1 2 2 0 1 2 2 0 1 2 2 1 0 2 2 3 2 3 0 2 2 1        48 New 5        0 2 2 1 0 2 0 2 2 1 2 3 2 1 0 2 0 2 2 1 2 1 2 1 2 3 0 2 2 1 2 3 2 1 2 1        48 32 Rassool et al.        1 2 3 1 2 0 0 3 2 2 3 2 2 3 0 0 0 2 2 1 1 2 0 2 2 0 3 2 2 1 0 0 2 3 2 1 0 1 0 3 2 1 2 0 3 0 0 2        52 New 6        0 2 2 1 0 2 0 2 0 2 2 1 2 3 0 1 2 1 2 3 0 0 0 2 2 1 0 2 2 3 0 1 2 3 2 1 2 1 0 3 2 1 2 1 2 1 0 1        52
Table 5:

n T States Code G G G Trace 7 16 New 7          0 2 2 1 2 1 0 2 0 2 2 1 2 3 0 2 2 3 2 1 2 3 2 3 2 1 2 3 2 1 2 3 0 2 0 2 2 3 2 1 0 2          56 8 16 New 8            0 2 2 3 2 3 0 2 2 1 2 3 0 2 0 2 2 3 2 1 2 1 2 3 2 1 2 3 2 1 2 1 0 2 0 2 2 1 2 1 0 2 2 1 2 3 0 2            64
Λ F 1 +Λ M 1 } Λ F 1 Λ F 1 Λ F 1 STATES: [x t-1 1 ,x t-1 2 ] [x t 1 ,x t 2 ]
time t time t +1

Λ M 1 = Y 0 Y 1 Y 2 Y 3 Y 4 + Λ F 1 = Y 4 Y 5 Y 6 Y 7 Y 8 + Λ F 1 = Y 8 Y

dN

  (d)d -n R , where N (d) is defined as the average number of error events with determinant d = det(A A A). The best codes must have the minimum value of η.

Figure 1 :Figure 2 :Figure 3 :Figure 4 :Figure 5 :Figure 6 :Figure 7 :Figure 8 :Figure 9 :

 123456789 Figure 1: Space-time trellis encoder for 4-PSK and n T transmit antennas Figure 2: Example of a trellis obtained for a 4 states 4-PSK STTC Figure 3: Example of a coset representation for a 4 states 4-PSK STTC Figure 4: Distance spectra of the optimal blocks of 2 columns in the case of 4-PSK modulation Figure 5: Example of a coset representation for a 16 states 4-PSK STTC Figure 6: Performance of 4/16/32 states 4-PSK STTCs with 5 transmit antennas and 2 receive antennas Figure 7: Performance of 4/16/32 states 4-PSK STTCs with 6 transmit antennas and 2 receive antennas Figure 8: Performance of 16 states 4-PSK STTCs with 7 & 8 transmit antennas and 2 receive antennas Figure 9: Performance of 8 states 8-PSK STTCs with 5 & 6 transmit antennas and 2 receive antennas

Figure 1

 1 Figure 1:

Figure 4

 4 Figure 4:

Figure 5 :

 5 Figure 5:

Figure 7 :

 7 Figure 7:

Figure 8

 8 Figure 8:

Figure 9 :

 9 Figure 9:

  The vector y y y i ∈ Z n T the least significant bit. In this example, the trellis representation corresponds to the generator matrix G G G = [y 1 y 2 |y 4 y 8 ].In the general case, for a 2 n -PSK STTC, there are 2 n transitions originating from a same state or merging into a same state. The MIMO symbols belong to Z n T 2 n .

	4	represents the
	MIMO symbol associated to an extended-state. The index i is computed as the decimal value of
	this extended-state, with x t 1,1

Table captions :Table 1 :

 captions1 Partition of the group Z 2 4

Table 2 :

 2

Table 3 :

 3 4-PSK STTCs based on the Euclidean distance criterion with 5 transmit antennas

Table 4 :

 4 4-PSK STTCs based on the Euclidean distance criterion with 6 transmit antennas

Table 5 :

 5 New 4-PSK STTCs based on the Euclidean distance criterion with 7 and 8 transmit antennas

Table 6 :

 6 New 8-PSK STTCs based on the Euclidean distance criterion with 5 and 6 transmit antennas

	Figure captions:

Table 6 :

 6

	n T	States	Code				G G G					Trace
	5	8	New 9	     	0 0 4 4 4	0 4 2 2 2	4 2 1 1 5	4 5 6 1 1	0 4 0 4 4	0 6 4 6 6	     	20.58
	6	8	New 10	      	4 4 4 0 0 0	6 6 6 4 4 0	5 5 1 6 2 4	0 4 4 6 2 2	0 0 0 4 4 4	4 6 2 1 3 7	      	25.17

  9 Y 10 Y 11 Y 12 + Λ F 1 = Y 12 Y 13 Y 14 Y 15 = Y 0 Y 16 Y 32 Y 48 Λ M 1 + Y 1 = Y 1 + Y 5 + Y 9 + y 13 Λ M 1 + Y 2 = Y 2 + Y 6 + Y 10 + Y 14 Λ M 1 + Y 3 = Y 3 + Y 7 + Y 11 + Y 15

				Figure 6:
	10 0
	10 -1
	FER
	-2 10			STATES: time t Rassool (4 states)	time t +1
				[x t-1 1 ,x t-1 2 ,x t-2 1 ,x t-2 2 ] [x t 1 ,x t 2 ,x t-1 1 ,x t-1 New 1 (4 states) 2 ] Rassool (16 states)
	10 -3	0	Y 16	2 New 2 (16 states) 4 Rassool (32 states) New 3 (32 states)	Λ M SNR (dB) 6 1 Y 8	8	10	12
			Y 20		Y 9
			Y 24	+Λ F 1	Y 10	+Λ M 1
			Y 28		Y 11
			Y 32		Y 12
			Y 36 Y 40	+Λ F 1	Y 13 Y 14	+Λ M 1
			Y 44		Y 15
			Y 48		Y 16
			Y 52 Y 56	+Λ F 1	Y 17 Y 18	+Λ M 1
			Y 60		Y 19