Gilles Hubert
email: hubert@iritfr

Yoann Pitarch

Karen Pinel-Sauvagnat'

Ronan Tournier

Léa Laporte

Toulouse Archive Ouverte

Keywords: IR Mode! Feature-based representatlon Tournament 1. Introduction

Numerous feature-based models have been recently proposed by the information retrieval community. The capability of features to express different relevance facets (query-or docu ment-dependent) can explain such a success story. Such models are most of the time supervised, thus requiring a leaming phase. To leverage the advantages of feature-based representations of documents, we propose TOURNARANK, an unsupervised approach inspired by real-life game and sport competition principles. Documents compete against each other in toumaments using features as evidences of relevanoe. Toumaments are modeled as a sequence of matches, which involve pairs of documents playing in tum their features. Once a toumament is ended, docu ments are ranked according to their number of won matches during the toumament. This principle is generic since it can be applied to any collection type. lt also provides great fl ex ibility since different alternatives can be considered by changing the toumament type, the match rules, the feature set, or the strategies adopted by documents during matches. TOURNAMNK was experimented on several collections to evaluate our mode! in different contexts and to compare it with related approaches such as Learning To Rank and fusion ones: the TREC Robust2004 collection for homogeneous documents, the TREC Web2014 (ClueWeb12) collec tion for heterogeneous web documents, and the LETOR3.0 collection for comparison with su pervised feature-based models.

Information retrieval (IR

) and ranking are inherently linked. Document ranking implies evaluating the relevance of documents according to a user need, expressed as a query. Pioneering models are based on manually tunable weighting sc hemes and matching functions such as BM25, Tf.Idf, or Cosine measure (Manning, Raghavan, & Schütze, 2008). More recent works intend to automatically determine these two facets of IR models. They mainly rely on a feature based representation of documents. Due to their variety, features used as relevance predictors enable a rich representatio n of potentially heterogeneous documents. The feature based works can fit into two main categories: supervised and unsupervised techniques. On the first hand, supervised approaches, lmown as Learning To Rank (LTR) methods (Tax, Bockting, & Hiemstra, 2015 ), have been thoroughly investigated in the literature and often offer very competitive performances provided that enough labelled training data are available (Macdonald, Santos, & Ounis, 2013). On the other hand and to the best of our lmowledge, very few works have investigated the use of features in an unsupervised scenario for adhoc retrieval. They have been proposed to fit very particular scenarios using most of the time linear combination of features.

Tournament 7

MatchM,B vs 8 f------.i Match M2B vs� Match M 3 B vs 8 Match M,8 vs B 8 VS @ Match Mn-3 8 VS @ Match Mn-2 � vs @ Match M._, � VS @ Match M. The rest of this article is organized as follows. Our ranking mode! is defined in Section 2. TOURNARANK applied as a reranking mode! is presented in Section 3. The experimental setup is described in Section 4. The experiment results are detailed and discussed in Section 5. Section 6 presents the related work and Section 7 finally concludes the article.

TOURNARANK mode!

Before formally defining TOURNARANK, we first illustrate the tournament principle through an example given in Fig. 1. Given a set of documents "If, each document d i E "If is represented by 6 features, denoted by / 1 to / 6 . A subset of "If is qualified to participate to the tournament. In our example, a document is qualifi ed if / 1 > O. Du ring the tournament, a sequence of matches between two docu ments is organized. During a match between d; and �. both documents play in tum their features. The better the feature values, the higher the chance to win the match. After the match, both documents eam points depending on their result (win, Joss, or draw). In the example, a document eams 3 points if it wins, 1 point in case of a draw, and O point if it !oses the match. At the end of the tournament, the total number of points each document has eamed is considered to rank documents. In our example, da is ranked before d 1 , d 1 � is ranked before ds and d2.

Model concepts and prelimina,y notntion

Let us consider a collection of documents "If, a set of features .P' = {{;}, and a query q. "tt .r is the set of qualified documents (according to q) for a tournament ff. In this article, documents are qualified according to the values of a given feature. A toumament ff is a sequence of matches between pairs of documents, i.e., ff = (M(d1, d2), M (d3, d1), ... ). As in sport competitions, many types of tournaments can be designed, e.g., soccer league or chess tournaments. Those used in the TOURNAI\ANK framework are de s cribed in Section 2.2. A match M(d. , dj) brings together two documents, d; and d 1 , according to a set of rules described in Section 2.3.2. Each document dis represented as a vector of feature values , denoted by /1, defined over .P'. Before each match, each document d is assigned the same initial life gauge, denoted by A, which decreases during the match according to the different strikes. When playing a match M(d 1, �), the document d 1 (resp. d 1 ) follows a strategy, denoted by <1a ; (resp. <1a) which consists in ordering its features into a list. This list as well as the adopted strategy will be indistinguishably denoted by ad in the rest of this article. The strategies a document can adopt are described in Section 2.3.3. The result of a match is a pair of integers (p i , p j ) such that p i (resp. p j ) represents the number of points awarded by document d i (resp. d j ). The number of points a document is awarded in case of a win (resp. a draw) is denoted by pw (resp. pd). A match can thus formally be represented by a function

C C T T × → × M
pw pd pw pd : { , , 0 } { , , 0 } . During a tournament T , documents accumulate points depending on the results of the matches they are involved in. The total amount of points a document d is awarded during a tournament T , is denoted by w d . Once the tournament is over, i.e., all the matches were played, documents are ranked according to their w d scores. Notation presented in this section as well as other notation presented below are summarized in Table 1.

Tournament definition

We now provide a description of different tournament types usually found in sport competitions and used in TOURNARANK.

Round Robin tournament

Given a query q, the Round Robin tournament, denoted by T RR is inspired by very well known sport competitions such as soccer championships. In this type of tournament, each participant, i.e., a document d i , plays against all the other participants C T ∈ d j

. The amount of points w di a document d i is awarded at the end of a tournament T RR is calculated as follows:

CT ∑ = = ∈ - w p p p Md d , with ( , ) ( , ) d d d i i j i j { } i j i
where p i is the number of points awarded to the document d i during its match against d j .

Swiss system tournament

The Swiss System tournament is inspired by chess tournaments 1 and aims at determining winners reliably, by performing less matches than the Round Robin tournament. Indeed each competitor does not play all the other competitors but only those belonging to its group (groups gather documents having the same number of points). Matches are scheduled one round at a time between competitors who have a similar current cumulative score, after each round of the tournament. Algorithm 1 describes the Swiss System Notation Definition

C

The collection of documents q

The query for which a ranking is produced T

The tournament associated with query q C T The set of documents qualified for T

F = f { } i
The set of features

f d
The feature vector of a document d over F

f i d
The value of the feature f i of d

φ i (x, y)
The distance function defined over the f i values ⪯ i

The order relation defined over the f i values M(d i , d j )

A match between documents d i and d j pw

The number of credited points in case of a win pd

The number of credited points in case of a draw (p i , p j )

The result of a match (the points credited to each document) σ ( • ) A document strategy type σ d

The strategy of document d following the strategy type σ ( • ) w d

The number of points a document d is credited during a tournament Λ

The initial life gauge of documents λ d

The life gauge of a document d during a match T RR Round Robin tournament with no boost factor T r ( )

SS

Swiss System tournament with r rounds, and no boost factor

T ρ N ( , )

PRR

Round Robin tournament with document pooling (ρ pools), selecting the top N% of each pool to compete in the final stage, and no boost factor T r ρ N ( , , )

PSS

Swiss System tournament with r rounds, document pooling (ρ pools), selecting the top N% of each pool to compete in the final stage, and no boost factor

T α ( ) u (•)
A tournament T (•) with upper weighting and boost factor α

T α X ( , ) s (•)
A tournament T (•) with seed weighting, boost factor α, and document being boosted if it wins over a top X% document in the initial ranking 1 https://en.wikipedia.org/wiki/Swiss-system tournament. tournament principles in our IR context. The number of rounds r is predefined. The first step of each round is grouping documents (line 3) into the group partition G . Grouping is performed w.r.t. the current sum of awarded points per document, w. Once groups are established, the pairing function (line 5) is called in descending order according to the number of points. Pairing is applied on groups composed of documents having the same amount of points, and proceeds as follows. Given a group G ⊆ G , w a graph with all documents in G w is created. Documents that have not played yet are connected. A Blossom based algorithm [START_REF] Edmonds | Paths, trees, and flowers[END_REF] is used to compute a maximal matching of the graph. Any unpaired document is added to the group with the next highest total number of points. The process is repeated until there are either one or zero unpaired documents. If there is one unpaired document, a bye is assigned and it will play during the next round. Each document can thus play at most one match per round. Once pairing P is performed, i.e., the matches are scheduled, matches are run (line 7) and awarded points are added (lines 8 9) to the current score w di (resp. w dj ) of the document d i (resp. d j ). This process is repeated until the number of rounds r is reached. Swiss System tournaments with r rounds are denoted by T r ( )

SS

in the rest of the article. Remark. A possible drawback of this tournament type is that, although top and bottom competitors are reliably determined with fewer rounds than with a Round Robin, the soft underbelly may be less reliable. However, this drawback is negligible if we focus on metrics evaluating the top ranked documents.

Two stage tournaments

A two stage tournament strategy adds a selection step to better identify documents that will be top ranked. As a side effect, this interestingly limits the number of matches and thus improves efficiency.

In a first stage, documents are assigned to ρ pools. The allocation is based on the feature that serves for the tournament quali fication to produce similar pools. The set of documents is split in three subsets (top ranked, mid ranked, and bottom ranked docu ments according to the qualifying feature). The documents belonging to each subset are randomly distributed to produce homo geneous pools. A (sub )tournament is then run within each pool. 2 In a second stage, the top N % documents with highest scores per pool are selected and an ultimate (sub )tournament is launched on these documents. Documents are eventually ranked according to their final scores. Round Robin and Swiss System tournaments using document pooling are respectively denoted by T ρ N ( , )

PRR and T r ρ N ( , , ) PSS .

Analysis of tournaments

From an efficiency point of view, the number of played matches can be critical. Given a tournament T (•) with C T documents, r rounds, ρ pools and N % documents selected per pool, the function T

C T f r ρ N ( , , , , ) (•)
that evaluates the number of matches is: When associated with two stage tournaments, the function/ is decomposed into two operands: the first one is dedicated to determine the number of matches during the pooling stage while the second operand determines the number of matches during the final tournament. In practice, for y PSS , the function f can be reduced to (N + 1). ,.11'; 1 . From these functions, it can be seen that the size of 'W .r plays a crucial role in the number of played matches. The behavior of these functions when varying the size of 'W .r is reported in Fig. 2. As expected, the number of matches is much lower for Swiss tournaments than for Round Robin ones. lt should be noted that the number of matches for Swiss toumaments is the worst case, because if a document cannot be paired during a round it does not play in this round. However, it is the exact number of played matches for Round Robin tournaments. The pooling strategy inherently introduces a last round in the tournament for the best documents. From an efficiency point of view, it is yet very beneficial to y PRR (p, N) since it drastically reduces the number of matches in each tournament that uses pools. However, the number of matches remains unchanged during the first stage of Swiss System tournaments that use pooling, which explains the lack of interest for pooling documents with Swiss System tournaments. We report execution times in Section 5.

T T C T T T T C C T T C T C T C T T T T ⎜ ⎟ ⎧ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ = ⎛ ⎝ ⎞ ⎠ = + = + = C i f r i f r ρ C C if ρ N ρ r ρ r N i f r ρ N • 2 ( ) • ( , ) • • 2 • 2 • ( ,, ) RR SS ρ N PRR PSS 2 (•) (•) 2 • 2 (•) (•) Input: C T ,
.... .. �-X *'"* <>-O •��---,•� •-------------------------- , ,)('
On the parallelization of tournaments. Efficiency can be again improved by considering that many matches can actually be run in parallel. We thus introduce the concept of match days as in soccer championships, i.e., a document plays at most one match during a match day. Fig. 3 displays the theoretical number of match days w.r.t. the tournament type.

Comparing Figs. 2 and 3, and assuming that the execution times of a match and a match day are comparable with parallelization, i.e., all the matches in a match day can be run simultaneously, one may infer that efficiency can be improved by at least ten times. For instance, if we consider T RR tournaments and C T =100, the execution time would be shortened from 5000 to 100.

Match definition

This section starts by discussing how feature values can be compared, then details the match rules, and finally presents the different strategies a document can use to compete against another document.

Feature value comparison

During matches, documents fight each other by comparing their feature values. It is thus necessary that, given a feature f i , their values are comparable. In this section, we introduce two key concepts associated to each feature: an order function, denoted by ⪯ i , to determine which document wins on a given feature, and a distance function, denoted by φ i , to determine the impact of each strike.

In this work, it is assumed that, for each feature f i , it exists a single optimal value conveying relevance, denoted by △ i , and a minimal one, denoted by ▽ i . Both the order and the distance functions depend on the position of △ i in the distribution of the feature values. Three cases should be considered:

Case 1 △ i is the highest value of the feature value distribution. This is typically the case when considering f i being the cosine value w.r.t. the query where the highest possible value is 1 and means a perfect fit between the document and the query, i.e., △ = 1 i . In this scenario, given two documents d and d′, we have

d⪯ i d′ if ≤ ′ f f i d i d and = ′ - ′ φ f f ( , ) i i d i d f f std f ( ) i d i d i
.

Here, we divide the difference between the two feature values by the standard deviation of f i to smooth the various feature distributions. Case 2 △ i is the lowest value of the feature value distribution.This is typically the case when considering f i being a distance to the query, e.g., the Euclidean distance, where the lowest possible value is 0 and means a perfect fit between the document and the query, i.e., △ = 0 i . In this scenario, given two documents d and d′, we have

d⪯ i d′ if ≥ ′ f f i d i d and = ′ - ′ φ f f ( , ) i i d i d f f std f ( ) i d i d i .
Case 3 △ i is neither the highest nor the lowest value of the feature value distribution. This is typically the case when considering f i being the dwell time [START_REF] Liu | Personalizing information retrieval for multi-session tasks: Examining the roles of task stage, task type, and topic knowledge on the interpretation of dwell time as an indicator of document usefulness[END_REF]. In this scenario, given two documents d and d′, we have

d⪯ i d′ if -△ ≥ -△ ′ f f i d i i d i and = -△ - -△ ′ ′ φ f f f f ( , ) i i d i d i d i i d i .
It may happen that given a document d, its value for feature f i is not available. In this case, we hypothetize that f i d is set to ▽ i , i.e.,

∀ ′ ⪯ ′ d f f i d i d .

Match rules

In a match, two documents face each other and play in turns their features. The general match procedure is presented in Algorithm 2. Initially, both documents start the match with their life gauges, denoted by Λ, at the same level (lines 3 4). Each document d ranks its features according to the strategy type denoted by σ ( • ) , which basically consists in ordering its features (document strategies are further described in Section 2.3.3) (lines 1 2). This results in the strategy followed by the document d, denoted by σ d .

The first document to strike is randomly chosen (line 5). When its turn comes, the document pops its next top remaining feature from its strategy (line 8 or 12). The Strike function is then called (Algorithm 3) where the other document gets its value of the same feature (f i ) and removes it from its document strategy (line 2). Both values are compared (line 2) and the life gauge of the document with the lowest value according to the order relation ⪯ i is then reduced by the distance φ i between the two feature values.

This process is repeated until either all features have been played or one document's life reached 0. At the end, the winner is the document having the highest life. Each win yields a gain of pw points for the winning document and 0 for the looser. In case of a draw, both documents yield a gain of pd points.

Let us illustrate these match rules using the documents in Fig. 4. In this example, each feature takes its values in the [0, 1] range , where 1 is the optimal value (case 1 in Section 2.3.1). Both documents d 1 and d 2 start the match with a life gauge = Λ 3 and with features ordered as shown in Fig. 4 (see strategies described in Section 2.3.3). For ease of reading, we assume that, ∀ = f std f , ( ) 0.5

i i
. Document d 1 is randomly chosen to start the match and strikes d 2 using feature f 1 (which is its "best" feature). As i.e., d 2 is dead, the document d 1 wins and gets pw points.

f d 1 1 (=0.9) is greater than f d 1 2 (=0.4),

Document strategies

During a tournament, all the documents adopt the same type of strategy, denoted by σ ( • ) . Intuitively, the strategy a document d adopts is the key element in determining how victorious it can be. There exists C T ! potential strategies. A naive one, named the order by value strategy and denoted by σ v , consists in playing features in descending order of feature values.

Input: λ X , λ Y , σ Y , f i Output: λ X , λ Y , σ Y 1 σ Y ← σ Y -{ f i }; 2 if f Y i i f X i then 3 λ Y ← λ Y -ϕ i ( f X i , f Y i ); 4 else 5 λ X ← λ X -ϕ i ( f X i , f Y i ); Algorithm 3. Strike(λ X , λ Y , σ Y , f i ). Input: Λ, d i , d j , σ (•) Output: (p i , p j ) 1 σ d i ← getStrategy(d i , σ (•) ); 2 σ d j ← getStrategy(d j , σ (•) ); 3 λ d i ← Λ; 4 λ d j ← Λ; 5 currentPlayer ← rand(d i , d j ); 6 while (λ d i > 0 and λ d j > 0) and (|σ d i | > 0 or |σ d j | > 0) do 7 if currentPlayer = d i then 8 f played ← pop(σ d i ); 9 S trike(λ d i , λ d j , σ d j , f played ); 10 if |σ d j | > 0 then currentPlayer ← d j ; 11 else 12 f played ← pop(σ d j ); 13 S trike(λ d j , λ d i , σ d i , f played ); 14 if |σ d i | > 0 then currentPlayer ← d i ; 15 if λ d i > λ d j then 16 return (pw, 0); 17 else if λ d j > λ d i then 18 return (0, pw); 19 else 20 return (pd, pd); Algorithm 2. M(Λ, d i , d j , σ ( • ) ). d 1 li /6 '3 '4 fs h >.,�a.o � �� §]�� Initial state: d 2 li fs '3 '4 !6 h >.4,'73.0 � §j � � §] §j d 1 li /6 h '4 /s h d 1 Ji /6 '3 /4 /s h ..- ,.,, "'ë',. , ), � § §1 � � = ���� JJ -0 >.,, = 2.8 0 C C :J :J 0 d 2 1 /s '3 '4 /6 h d 2 a.
a:

li /s '3 '4 /5 h w >..,�2.0 � §] � � §] §] -==> ���� §] §] >. 4, = 0.9 d 1 f /6 '3 /4 fs h d 1 f /5 '3 /4 /s h N = ���� = ��;, §]�� JJ -0 .1..., =2. 8 >.,, = 2.8 0 C C :J :J 0 d 2 d 2 fi /s 3 /4 /6 h a.
a: The order by ranlc strategy for d 1 is /1, / 4 , / 6 ,'3, '2, / 5 and for d2 is /s, '3, /1, f 4 , f 6 , fz. Supervised strategies can also be elaborated. Sorne of them were experimented, e.g., ranking features according to their entropy, Gini index, or NDCG. Since results were very similar to the unsupervised strategies, they are not presented. We leave for future work strategy adaptation during a match or a tournament.

f fs h '4 /6 h .i,.. = � §]�� §] §] >..,�0.1� � � � � §1 >.

4. Discussion

At this point, it is worth positioning our model w.r.t. the state of the art. First, TOUI\NAI\ANK may be related to the fusion methods if one views each featur e as a list generator. In both cases, the order induced by feature values is essential for the final ranking of documents. Second, as Learning To Rank (L1R) approaches, our model relies on a feature based representation of documents. However, as opposed to LTR approaches TOUI\NARANK is fully unsupervised. Third, as only a subset of documents is qualified to participate to the tournament and as this qualification may depend on an initial ranking that may be used during matches, TOURNARANK can fall into the reranking category of approaches as detailed in Section 3. Finally, although documents fight each other in different games, TOUI\NARANK does not rely on game theory [START_REF] Zhai | Towards a game-theoretic framework for information retrieval[END_REF].

TOURNARANK as a reranking model

As aforementioned, TOUI\NARANK can be easily used as a reranking model Indeed, given a query, a tournament can be run on an already ranked set of documents. In this case, the list to be reranked is the one induced by the feature used in the qualification step (/ 1 in the example of Fig. 1). In other terms, 'W .r is considered as an ordered set, such that d; > � if d 1 is better ranked than � according to the qualifying feature.

One can argue that the initial ranking should be taken into account in the match results. Particularly, an advantage should be given to the documents that win against an initially better ranked document. This can be done by introducing a boosting factor a > 1 that favors initially low ranked documents against higher ranked ones. This boosting factor can be used in two different scenarios: Upper boost and Seed boost. In the Upper boost scenario the number of points awarded to the winner is boosted if it is initially lower ranked than its opponent. In the Seed boost scenario the number of points awarded to the winner is boosted if its opponent is ranked in the top X% of the initial ranking. To fit this boosting definition, Algorithm 2 has to be modified into Algorithm 4. In the rest of the article, a tournament with no boost is denoted by T (•) (with

∈ RR SS PRR PSS (•) { , , , }), while upper (resp. seed) boost is denoted by T α ( ) (•) u (resp. T α X ( , ) (•) s
).

Experimental setup

We ran various experiments using the two collections Robust2004 and Web2014 provided in the context of the TREC evaluation campaigns as well as the LETOR 3.0 collection. The experiments aimed to evaluate various variants of our approach, i.e., varying several components, to answer several evaluation questions.

Questions

The following four evaluation questions Q1 Q4 guided the various experiments presented in the remainder of the paper. Q1 How does the set of features, considered as document skills, impact ranking? (see Section 5.1) Q2 What is the impact of the different parameters in terms of effectiveness and efficiency? (see Section 5.2

) Feature Document f 1 f 2 f 3 f 4 f 5 f 6 d 1 2 7 4 2 7 3 d 2 8 1 0 7 8 5 9 Input: Λ, d i , d j , b, α Output: (p i , p j )
1 Execute lines 1 to 14 of Algorithm 2. Then: Q3 Which parameter combination yields effective ranking? (see Section 5.3) Q4 Do document competitions outperform data fusion methods or LTR ones ? (see Section 5.4)

2 if λ d i > λ d j

Collections

We used 9 different datasets for experiments, with a total of 981 queries:

• The Robust2004 collection provided for the TREC 2004 Robust Retrieval Track. The corpus is composed of 528,155 homogeneous documents (disks 4 and 5 without Congressional Record CR documents). 249 topics are available [START_REF] Voorhees | Overview of the TREC 2004 Robust Track[END_REF]).

• The Web2014 collection provided for the TREC 2014 Web Track. This collection is commonly considered as a large scale col lection of heterogeneous documents. It is composed of the ClueWeb12 full dataset,3 which comprises 733 million pages (27.3 TB), and a total of 50 topics (Collins Thompson, [START_REF] Collins-Thompson | TREC 2014 Web Track Overview[END_REF]).

• The LETOR 3.0 collection provided by Microsoft Research for evaluating and comparing LTR algorithms.4 It is composed of 7 datasets, one based on the Ohsumed collection and the others based on the ".gov" collection (HP2003, HP2004, NP2003, NP2004, TD2003, TD2004). Each dataset provides from 50 to 150 topics (a complete description is available in Liu, 2011).

Feature description

Depending on the collection, we used different sets of features. For Ohsumed and ".gov", we directly used the features from the LETOR 3.0 datasets [START_REF] Liu | Learning to rank for information retrieval[END_REF] (Ohsumed provides 45 features versus 64 for the ".gov" collection). 13 features were defined for the Robust2004 collection. Features f 1 to f 10 are usual features used in LTR, taken from [START_REF] Liu | Learning to rank for information retrieval[END_REF]. Features f 11 , f 12 , and f 13 correspond to the state of the art models implemented in Indri,5 i.e., feature f 11 corresponds to Tf.Idf, feature f 12 corresponds to Okapi, and feature f 13 corresponds to the Indri model, which is a combination of language modeling and inference network retrieval frameworks [START_REF] Metzler | A feature-centric view of information retrieval[END_REF]. These 13 features were also used for the Web2014 collection, complemented with two Web specific features (i.e., PageRank and spam scores 6 ). According to their definitions, features are categorized into three classes: Query In dependent (F QI ), Query Dependent (F QD ), and Model (F M ). The features associated to the Robust2004 and Web2014 collections are summarized in Table 3. All the features fall into the case 1 described in Section 2.3.1, were normalized between 0 and 1 using a max normalization, and were evaluated on whole documents.

f 1 ∑ ∈ ∩ TF t d ( , ) t i q d i √ √ F QD f 2 ∑ ∈ ∩ IDF t ( ) t i q d i √ √ F QD f 3 ∑ ∈ ∩ TF t d IDF t ( , )• ( ) t i q d i i √ √ F QD f 4 ∑ ∈ ∩ TF t d log( ( , )) t i q d i √ √ F QD f 5 LEN(d) √ √ F QI f 6 ∑ ∈ ∩ t i q d TF t i d LEN d ( , ) ( ) √ √ F QD f 7 ∑ ∈ ∩ t i q d log TF t i d LEN d (( ( , )) ( ) √ √ F QD f 8 ∑ + ∈ ∩ ( ) log 1 t i q d C TF t i C ( , ) √ √ F QD f 9 ⎟ ∑ ⎞ ⎠ ∈ ∩ TF t d log C IDF t ( , )•( ( . ( )
t i q d i i √ √ F QD f 10 ∑ + ∈ ∩ ( ) log • 1 t i q d TF t i d LEN d C TF t i C ( , ) ( ) ( , ) √ √ F QD f 11 Tf.Idf (Indri implementation) √ √ F M f 12 Okapi-BM25 with = k1 1.2 = b 0.75, and = k3 7 (Indri implementation) √ √ F M f 13 Indri proper model √ √ F M f 14 PageRank √ F QI f 15 Spam score √ F QI
validation methodology are given in Section 5.4. It should be recalled that contrary to LTR approaches, TOURNARANK is an un supervised approach. The cross validation is here applied to select the best parameter combination to apply on the test dataset. These 3 variants were chosen to optimize the P@20 metric since this metric looks consistent to evaluate the quality of a reranking approach.

Competitors. Since TOURNARANK may be related to data fusion methods, we compared it with state of the art rank and score aggregation methods (Borda (de Borda, 1781), RRF with k=60 [START_REF] Cormack | Reciprocal rank fusion outperforms condorcet and individual rank learning methods[END_REF], CombMNZ, and CombSum [START_REF] Fox | Combination of multiple searches. The second text retrieval conferenceTREC-2500-215[END_REF]). We also compared our unsupervised approach to standard supervised ones, using 8 standard LTR methods (MART, RankNet, RankBoost, AdaRank, Coordinate Ascent, LambdaMART, ListNet, and Random Forests) that were executed on the 50 documents described previously. 8 These LTR methods were trained to optimize the P@20 metric to be fairly compared to TOUR-NARANK. A direct use of learning to rank methods included in LETOR 3.0 was not possible since the results are reported using up to 1000 documents per topic whereas we choose to qualify 50 documents.

Results

The representative results are reported here and serve as basis to answer the aforementioned research questions.

Impact of the feature set

The results varying the feature set (see Fig. 5) provide answers to Q1. For brevity, the results are reported regarding the P@20 metric only. Similar conclusions can be drawn regarding the results over the other metrics, i.e., MAP and MRR. Generally, one can notice that the results are consistent on both collections. The only exception is when using the query independent features only (F QI ). Indeed, the results are poor on the Robust2004 dataset whereas they are satisfactory on the Web2014 dataset. This can be easily explained since the only query independent feature on Robust2004 is the document length which is not sufficient to correctly rerank documents. Alternatively, in case of Web documents, more sophisticated features, i.e., PageRank and Spam score, tend to be reliable relevance clues. In both cases (Web2014 and Robust2004), the best performances are obtained when considering F , M QI , i.e., using model and query independent features. This motivates the need for considering heterogeneous feature types. Indeed, as shown by the results of F M QI , vs. F , M QD , the benefits of combining high quality query dependent features (F M ) and query independent features (F QI ) are higher than when combining features relying on the same concepts, i.e., TF and IDF (F M and F QD ). Finally, TOURNARANK is robust when considering the full set of features if it contains high quality features, i.e., F M . Indeed, if we consider all the features (F All ), the results slightly deteriorate. Consequently, the often costly feature selection step does not seem to be mandatory when running TOURNARANK over an unknown collection.

Impact of the TOURNARANK parameters

The results varying the TOURNARANK parameters (see Figs. 6 9) provide answers to Q2 in terms of effectiveness. Tournament type. In Fig. 6, we can see that effectiveness is quite similar whatever the considered tournament type on both Fig. 10. Efficiency varying the tournament type (seconds).

Table 5

Comparison of 3 TOURNARANK variants with learning to rank and data fusion methods on the Web2014 and Robust2004 collections. For each collection, the fourth (resp. fifth) line presents results for the best (resp. worst) LTR method while the sixth line presents the results for the best data fusion method. † and ⋆ denote significance (p < .05) with respect to INDRI and the best data fusion method respectively. These symbols are doubled when p < 0.01. Randomization tests were not performed on the LTR methods. collections. However, results are more variable on Robust2004. This is related to the observations discussed before about the impact of the feature set, i.e., a non negligible number of experiments where run using F QI which leads to poor results. This observation holds for the rest of this section. We will discuss the default tournament type we recommend at the end of this section after having considered the efficiency aspect. Boosting technique. In Fig. 7, we can see that the boosting technique does not significantly impact effectiveness. Consequently, running TOURNARANK without boosting seems to be a better choice since it does not imply the setting of extra parameters.

Run

Impact. In Fig. 8, we can see on both collections that applying the φ i function leads to slightly better results than systematically decreasing the life gauge by 1. This shows the interest of an impact based on feature values rather than simply based on the order function. This motivates the investigation of subtle φ i functions, left as future work.

Strategy type. In Fig. 9, we can see that the strategy type does not significantly impact effectiveness. This may be due to the similarity in top positions between the two generated feature rankings. Whatever the initial life gauge of documents, the same features are played leading thus to similar results.

Efficiency. A counterintuitive observation can be done analyzing Fig. 10. The Swiss system tournaments are more time consuming than the Round Robin ones. This is due to the pairing phase (line 5 of Algorithm 1) that counterbalances the gain regarding the number of matches. As expected (see Section 2.2.4), pooling documents leads to a better efficiency in all the cases. To conclude we suggest considering pooling Round Robin tournaments, which meets a good trade off between efficiency and effectiveness.

Table 6

Comparison of 3 TOURNARANK variants with learning to rank and data fusion methods on the LETOR collections. For each collection, the fourth (resp. fifth) line presents the results for the best (resp. worst) LTR method while the sixth line presents results for the best data fusion method. † and ⋆ denote significance (p < .05) with respect to the initial ranking and the best data fusion method respectively. These symbols are doubled when p < .01. Randomization tests were not performed on the LTR methods.

Run

Comparison of TOURNARANK configurations

In this section, we compare three different versions of TOURNARANK:

• TOURNARANK (median) corresponds to the parameters fixed according to the best median results in Figs. 69: F M QI , (for Web2014 and Robust2004), 9 T (2, 20),

PRR T = = α X ( 3, 10), (•) s distance ( = ∞ Λ ), σ r .
• TOURNARANK (max) corresponds to the parameters fixed according to the best max results in Figs.

T = = α X ( 3, 20), (•) s distance ( = Λ 200%), σ r .
• TOURNARANK (cross) corresponds to a 5 fold cross validation considering the 50% best parameter values regarding median results union the 50% best parameter values regarding max results. The best configuration obtained on the training set was launch on the test set for each fold. Those parameters are in bold in Table 4.

It should be noted that for Web2014 and Robust2014, data fusion methods were run on F M QI , for fair comparison with TOURNARANK.

The results shown in Tables 5 7 provide answers to Q3.

The static configurations (max and median) obtain similar results w.r.t. all the evaluated metrics. Given that the max config uration slightly obtain better results, we advice to use this one as a preliminary choice on a new collection. Even better, this configuration performs better than when performing a cross validation to learn collection appropriate parameter values. Indeed TOURNARANK (max) yields better results than TOURNARANK (cross) on all the metrics on 4/9 datasets and on at least two metrics on almost all datasets (8/9). This shows that the max configuration is a robust configuration since it has been obtained from Robust2004 and Web2014 results while performing well on all the LETOR datasets.

Comparison with baselines and competitors

In this section, we compare the three aforementioned versions of TOURNARANK with the best and worst learning to rank competitors as well as with the best data fusion one over nine datasets. Results are summarized in Tables 5 7 and provide answers to Q4.

Table 7

Comparison of 3 TOURNARANK variants with learning to rank and data fusion methods on the LETOR collections. For each collection, the fourth (resp. fifth) line presents the results for the best (resp. worst) LTR method while the sixth line presents results for the best data fusion method. † and ⋆ denote significance (p < .05) with respect to the initial ranking and the best data fusion method respectively. These symbols are doubled when p < .01. Randomization tests were not performed on the LTR methods. (6/9). Moreover, on four datasets (Web2014, Robust2004, NP2003, and NP2004), all the three metrics are improved by TOURNARANK. Fusion methods. With regard to the data fusion methods, TOURNARANK is most of the time more effective on the three metrics (5/ 9). When TOURNARANK fails in outperforming the best fusion method the performance is not statistically significant except in one case (Web2014). Moreover, on HP2003, the best fusion method failed in improving the initial ranking as well. In all the cases, TOURNARANK performs better than the worst data fusion method (not reported in Tables 5 7 since systematic). Finally, it should be noted that TOURNARANK systematically outperforms the best fusion methods using all the features on the Web2014 and Robust2004 collections. These results are not presented in the tables for clarity purpose.

Run

LTR techniques. TOURNARANK systematically outperforms the worst LTR on MRR and P@20. Even better, TOURNARANK outperforms the worst LTR on all the metrics on 4/9 datasets (NP2003, NP2004, HP2003, and HP2004). Let us now compare TOURNARANK with the best LTR approaches. Even if they perform much better on the MAP metric, TOURNARANK systematically yields better results on the MRR and obtains comparable results according to P@20. It is interesting since LTR approaches have been trained to optimize the P@20 metric.

Discussion

Now we have carefully detailed our experiment results, we further analyze the implications of our results:

• Globally, TOURNARANK performs well on all the evaluated collection types. The results do not show any noticeable differences relative to the collection types (homogeneous or heterogeneous collections such as the Web2014 collection).

• The results of TOURNARANK are comparable to the best data fusion ones.

• TOURNARANK improves the initial ranking on P@20 and MRR, and is thus an effective reranking method on homogeneous and heterogeneous collections.

• Our best results on the P@20 and MRR metrics bear the idea that the top part of the ranking produced by TOURNARANK is of high quality. However, our more contrasted results on the MAP metric indicate that TOURNARANK has trouble identifying relevant documents in the soft underbelly of the initial list. A possible explanation of this phenomenon is that top ranked documents won their matches thanks to some high valued features. Moreover, when documents are represented by a majority of feature values close to the mean, TOURNARANK inherently experiences difficulties in distinguishing their relevance. This paves the way for more sophisticated document strategies.

• TOURNARANK is robust when considering the full set of features if it contains high quality features. Indeed, if we consider all the features (F All ), the results slightly deteriorate. Consequently, the often costly feature selection step does not seem to be mandatory when running TOURNARANK over an unknown collection.

• A recommended configuration has emerged from our results (max, see Section 5.3).

• This configuration have been obtained without any learning step and therefore can be used on any new datasets contrary to LTR approaches that require an available ground truth.

Related work

In this article we propose a novel approach to rank documents, by making them challenge each other, based on their feature values during matches. Since we consider a feature based representation of documents and use some IR model scores as features, one may see similarities with the data fusion methods and the learning to rank ones. Furthermore, as only a subset of documents is qualified to participate to the tournament and as this qualification may depend on an initial ranking that may be used during matches, TOURNARANK can fall into the reranking category of approaches. In this section, we thus present the major document reranking approaches and then introduce the principles and major works in data fusion and learning to rank. Finally, the similarities and differences with our method are discussed.

Document reranking

Document reranking aims to reorder a list of documents retrieved by a search engine to improve the overall quality of this list, according to a given evaluation measure, e.g., P@k, MAP, MRR. In the literature, the reranking approaches lie in two categories [START_REF] Ye | Incorporating rich features to boost information retrieval performance: A svm-regression based re-ranking approach[END_REF]. The first category gathers resource based approaches which use additional information or resources to rerank documents. These resources are for instance a thesaurus [START_REF] Qu | Rerank method based on individual thesaurus[END_REF], or in personalized search, user preferences [START_REF] Daoud | A session based personalized search using an ontological user profile[END_REF][START_REF] Fathy | A personalized approach for re-ranking search results using user preferences[END_REF] or user behaviors [START_REF] Cai | Personalized document re-ranking based on bayesian probabilistic matrix factorization[END_REF]. Other methods, called graph based, use inter document relations as additional information source, by building a graph of documents, using relations such as bibliographic relations [START_REF] Picard | A logical information retrieval model based on a combination of propositional logic and probability theory[END_REF][START_REF] Salton | Advanced feedback methods in information retrieval[END_REF] or, in a Web context, hyperlinks. Hits [START_REF] Kleinberg | The web as a graph: Measurements, models, and methods[END_REF] and PageRank [START_REF] Page | The pagerank citation ranking: Bringing order to the webTechnical Report 1999-66[END_REF] are the first state of the art algorithms using such graphs. These approaches were generalized by [START_REF] Balinski | Re-ranking method based on inter-document distances[END_REF] to allow the use of any inter document relation with any retrieval model. The relationships are thus expressed by distances and can be obtained from the text, hyperlinks or other information. In [START_REF] Kurland | Pagerank without hyperlinks: Structural re-ranking using links induced by language models[END_REF], a graph is recreated if hyperlinks are not available in the document collection. The second group of approaches uses only documents as information source and our method belongs to this category. These approaches use several kinds of document features. In [START_REF] Zhang | Search result re-ranking by feedback control adjustment for time-sensitive query[END_REF], the document dates when queries are time sensitive. In [START_REF] Ye | Incorporating rich features to boost information retrieval performance: A svm-regression based re-ranking approach[END_REF], "richer" features are used, such as document length, average proximity of query terms, word features, or a Mitra equation [START_REF] Mitra | Improving automatic query expansion[END_REF]. However, this latter approach is based on a learning method, where the documents used for the learning process are pseudo relevant and non relevant documents. In [START_REF] Zheng | Re-ranking documents based on query-independent document specificity[END_REF], each document is analyzed independently and a specificity score, based on the normalized inverse document frequency and the term entropies, is evaluated. In [START_REF] Lee | Re-ranking model based on document clusters[END_REF], documents are analyzed using document clusters, some of the clusters being tailored to the characteristics of the query.

Data fusion

Data fusion aims to combine multiple information resulting from different retrieval models or different query formulations, in order to provide the user with an improved and consensual list of results [START_REF] Wu | A geometric framework for data fusion in information retrieval[END_REF]. This list is obtained by aggregating either ranks or scores in an unsupervised way. Rank aggregation methods can be grouped into three categories: distributional based, heuristic, and stochastic optimization algorithms [START_REF] Lin | Rank aggregation methods[END_REF]. In IR, the most widely used are heuristic algorithms. They mainly aim to aggregate a small number of long lists. Among the most popular in IR, one can cite Borda (de Borda, 1781), Condorcet (de Condorcet, 1785), RRF [START_REF] Cormack | Reciprocal rank fusion outperforms condorcet and individual rank learning methods[END_REF], or Markov chain methods [START_REF] Dwork | Rank aggregation methods for the web[END_REF]. The relevance score aggregation methods require a scoring function for each ranked list and then combine, for each document, its scores and rank the document according to this aggregated score. The most known algorithms in IR are CombSum, whose the aggregated score is the sum of the document scores on ranked lists, and combMNZ, whose aggregated score is based on combSum and takes into account the number of systems that retrieved the document [START_REF] Fox | Combination of multiple searches. The second text retrieval conferenceTREC-2500-215[END_REF]).

Learning to rank

Learning to rank (LTR) aims to automatically optimize a ranking function using a machine learning algorithm and learning data, in order to rank documents or web pages according to their relevance for a given query [START_REF] Li | Learning to rank for information retrieval and natural language processing[END_REF][START_REF] Liu | Learning to rank for information retrieval[END_REF]. Learning data consist of query document pairs represented as feature vectors and associated to relevance judgments given as ground truth. Standard features are similarity scores obtained by IR models such as BM25 or language models. As a supervised learning task, LTR is composed of a training phase and a testing phase. In the training phase, the LTR algorithms use learning data to learn a ranking function that provides an optimized list of results. In the testing phase, the ranking function is used to predict the relevance of documents for unseen queries. A ranked list is thus obtained and is compared to the ground truth by using an evaluation measure. Several ap proaches have been proposed to solve the LTR task, among them are the regression based algorithms [START_REF] Cossock | Subset ranking using regression[END_REF], the classification based algorithms [START_REF] Nallapati | Discriminative models for information retrieval[END_REF], the pairwise classification based algorithms such as RankNet [START_REF] Burges | Learning to rank using gradient descent[END_REF], RankBoost [START_REF] Freund | An efficient boosting algorithm for combining preferences[END_REF], and RankSVM [START_REF] Chapelle | Efficient algorithms for ranking with svms[END_REF][START_REF] Joachims | Optimizing search engines using clickthrough data[END_REF], as well as the algorithms that directly optimize IR evaluation measures, e.g., AdaRank [START_REF] Xu | Adarank: A boosting algorithm for information retrieval[END_REF], or permutation counts in the ground truth list, e.g., ListNet [START_REF] Cao | Learning to rank: From pairwise approach to listwise approach[END_REF].

Discussion

Contrary to the data fusion methods that aggregate various ranked lists based on either the ranks or the scores of documents, our approach considers a single list of documents. TOURNARANK could nevertheless be seen as a fusion method when considering each feature as a list generator. One can point out some similarities between our approach and LTR. Indeed, both approaches represent documents in a feature space, using similar features. Moreover, a match between two documents can be seen as a pairwise comparison of documents based on their feature values, which might remind the reader with pairwise LTR. However, the major difference is that our approach is unsupervised, whereas LTR is a supervised learning task. Contrary to LTR, our approach does not require a training phase to learn a ranking function. Finally, with some configurations, TOURNARANK is clearly a document reranking method.

Conclusion

Summary

In this article, we introduced TOURNARANK, a new and original unsupervised approach for document ranking which is not dedicated to a specific collection or domain. The documents are represented as feature sets which are then used by the documents to fight each other during matches organized in tournaments. The high flexibility and genericity of the model enables its adaptation to the reranking task. Our results on three state of the art collections, i.e., TREC Robust2004, TREC Web2014, and LETOR 3.0, are very encouraging and enable investigating promising research lines. Before highlighting them, we now discuss some implications of our research.

Implications

From a practical point of view, the previously presented results show that a pre processing step for feature selection is not vital to make TOURNARANK effective. Second, TOURNARANK does not require any labeled data since it is fully unsupervised. It consequently does not suffer from the well known cold start problem. Third, the model is highly parallelizable since matches can be played simulta neously during Round Robin tournaments and per match day in Swiss tournaments.

From a theoretical point of view, TOURNARANK being a generic ranking model, it can therefore be applied on other IR domains from the moment documents can be described through features. For instance, TOURNARANK can be applied to image retrieval since images can be described by a variety of features (see Deselaers, Keysers, and Ney, 2008 for details). The match and tournament principles proposed in this article still hold for such data types. Another aspect of the TOURNARANK model is that it can be adapted to the aggregated search problem in the sense that different types of documents, e.g., images, videos, tweets, and web pages, can confront themselves. This idea is part of our future work and is thus further introduced in the next section.

Future work

Two directions are considered: model improvement and its evolution to the aggregated search issue. Regarding model im provement, TOURNARANK is totally new, highly modular, and some intuitive instances of the general framework presented here, i.e., the tournament type, the match rule, the feature set, and the document strategy, were studied in this article. However other possibilities remain uninvestigated. We first aim to evaluate other document features, that should be more heterogeneous and complementary than the ones presented here. Among them one may cite features related to credibility [START_REF] Weerkamp | Credibility-inspired ranking for blog post retrieval[END_REF], readability [START_REF] Polajnar | Detection of news feeds items appropriate for children[END_REF], or the information quantity delivered by documents (Shannon entropy (Shannon, 2001)). Second, alternative tournament types, e.g., introducing multi stage tournaments, or match rules, e.g., where documents are not playing in turn, can be considered. Finally, we aim at enabling documents to learn their own strategies from past strikes/matches and to dynamically adapt their strategy during a match or a tournament.

For now TOURNARANK is only suited for ranking textual documents. The aggregated search issue has recently emerged within the IR community. Aggregated search attempt to achieve diversity by presenting search results from different information sources, e.g., images, blogs, or videos [START_REF] Arguello | Aggregated search[END_REF][START_REF] Kopliku | Aggregated search: A new information retrieval paradigm[END_REF][START_REF] Lalmas | Aggregated search[END_REF]. The challenge is to identify the subset of heterogeneous documents that best fits the user's need. To tackle this challenge, the TOURNARANK model can consider tournament between teams of heterogeneous documents. It raises some open questions related to team composition, e.g., introducing diversity or complementary criteria in team building, as well as the redefinition of the match concept when teams instead of in dependent documents fight themselves.

Fig. 1 .

 1 Fig. 1. Mode! overview.

  the work presented in this article is twofold: (1) taking advantage of a feature based representation of documents to leverage on multiple facets of relevance in a generic unsupervised manner, and (2) go beyond the simple query document matching, by introducing a pairwise document comparison for ranking. The research objective of this article is thus to explore a new line of research taking benefits from featJ.u"e based document represenmtions. To fulfil this research objective, we propose TOURNARANK, an unsupervised mode! drawing inspiration from principles of real life games and sport competitions. Documents, re presented by a set of features, oppose each other and gain points during matches organized in tournaments. The features are used as attack and defense characteristics during matches. Features can be for instance the PageRank, query term frequencies or ret rieval scores according to common IR models. Documents are then ranked according to the final score board of the tournament. To the best of our knowledge, this is the first method in the literature based on these principles. The main strength of TOURNARANK is its high flexibility, sinoe one can tweak (1) the document representation, i.e., the set of features considered for describing the document; (2) the tournament type (possibly considering an initial ranking); and (3) how documents compete against each other. We designed extensive experiments intended to give answers to various questions related to the concepts underlying our mode!, i.e., features, matches, and tournaments. Severa! collections are used in order to evaluate our mode! in different contexts (homogeneous vs het erogeneous documents and supervised vs unsupervised approaches): the TREC Robust2004, the TREC Web2014 (QueWeb12), and the LETOR3.0 collections.

Fig. 3 .

 3 Fig. 3. Number of match days w.r.t. the tournament type.

.

  we thus have after the round = f 1 is then removed from both document strategies, and d 2 continues playing using f 5 , resulting with the following values of λ:

  Fig. 4. Match example with A = 3.0.

  upper and d j > d i then 4 return (α * pw, 0); 5 else if b = seed and d i in the top X% then 6 return (α * pw, 0); , pd); Algorithm 4. M(Λ, d i , d j , b, α).

Fig. 5 .

 5 Fig. 5. Results varying the set of features (P@20).

Fig. 6 .

 6 Fig.6. Results varying the tournament type (P@20).

Fig. 9 .

 9 Fig. 9. Results varying the strategy type (P@20).

Fig. 7 .

 7 Fig. 7. Results varying the boosting technique (P@20).

Fig. 8 .

 8 Fig. 8. Results varying the impact (P@20).

Table 1

 1 Notation used throughout the article.

  Partition C T into groups s.t. w d i = w d j = w, ∀{d i , d j } ⊆ G w with G w ∈ G; A sub-tournament is a tournament as defined previously, but run only over a subset of documents in C T .

		r 5000
		Output: C T ordered by decreasing document score
	1 n ← 0 ;
	2 while n < r do 4000
	3 G ← 4 foreach G w ∈ G in descending order w.r.t. w do 5 P ← Pairing(G w ); 6 foreach (d i , d j ) ∈ P do :Û 3000 .i::.
	7 8	(p i , p j ) ← M(d i , d j ); w d i ← w d i + p i ; E =Il: 2000
	9	w d j ← w d j + p j ;
	10	n← n+1; 1000
		Algorithm 1. Swiss-System tournament algorithm.
		100
		80
		� 60
		"O
		E 40 =Il:
		20

2

Table 2

 2 Document rankings according to the features f 1 to f 6 for d 1 and d 2 .

Table 3

 3 Description of the 15 features used for experiments on the Web2014 and Robust2004 collections. F QD F QI and F M respectively stand for Query-Dependent, Query- Independent and Model features.

	ID	Feature

  Initial ranking. A global remark is that TOURNARANK yields effective reranking w.r.t. at least one metric, i.e., MAP, P@20, or MRR, on most of the datasets

			MAP	P@20	MRR
	TD2003	TOURNARANK (median)	0.1762	0.0980	0.4481
		TOURNARANK (max)	0.1760	0.1020	0.4505
		TOURNARANK (cross)	0.1634	0.0970	0.4376
		RankBoost	0.3929	0.1220	0.3400
		ListNet	0.2669	0.0770	0.1200
		CombMNZ	0.1757	0.1010	0.4444
		Initial ranking	0.1816	0.0970	0.4535
	TD2004	TOURNARANK (median)	0.1474 ⋆⋆	0.1613	0.4607
		TOURNARANK (max)	0.1479 ⋆⋆	0.1613	0.4650 ⋆
		TOURNARANK (cross)	0.1366	0.1587	0.4671 ⋆
		LambdaMART	0.4193	0.1827	0.4267
		ListNet	0.2345	0.0913	0.1600
		CombMNZ	0.1309 †	0.1600	0.4010
		Initial ranking	0.1513	0.1620	0.4646
	OHSUMED	TOURNARANK (median)	0.2523 † †	0.4349	0.6719 †
		TOURNARANK (max)	0.2525 † †	0.4363	0.6740 †, ⋆
		TOURNARANK (cross)	0.2574 †, ⋆	0.4363	0.6738 †
		RankBoost	0.5363	0.4429	0.6226
		MART	0.4978	0.4165	0.5566
		RRF	0.2480 † †	0.4325	0.6370 † †
		Initial ranking	0.2675	0.4453	0.7342

http://www.lemurproject.org/clueweb12.php/.

http://research.microsoft.com/en-us/um/beijing/projects/letor//letor3dataset.aspx.

http://www.lemurproject.org/doxygen/lemur/html/IndriRunQuery.html.

http://lemurproject.org/clueweb12/related-data.php.

A pilot study was conducted and showed that considering a life gauge ≥ 200% is similar to ∞. For clarity purpose we thus only provide results for these initial gauge values.

For the other datasets, i.e., the LETOR3.0 collection, F All was used for fair comparison w.r.t. LTR methods.

Protocol

The parameter values used to evaluate our model are described in Table 4. One can refer to Table 1 for a notation remainder. Concerning the impact, two main cases are evaluated: systematically decreasing the life gauge by 1 (denoted 1 in the table) or applying the φ i function, i.e., φ i is the normalized distance between two feature values (case 1 in Section 2.3.1). Several values of the initial life gauge Λ are considered:

• when decreasing the gauge by 1, the initial gauge is set to 20% or 50% of the number of features (i.e., a document can be dead before all the features have been played), as well as ∞, i.e., all the matches are completely run using all the features.

• similarly, when decreasing Λ using the φ i function, we set the initial gauge to 100%, 200% of the number of features, or ∞. 7 The applied percentage is ≥ 100 since the impact for each feature is in this case ≥ 1.

In all experiments pw (resp. pd) was set to 3 (resp. 1) following the rules of soccer leagues which aim to promote victories over draws.

All the runs were evaluated w.r.t. effectiveness computed using some usual measures (MAP, P@20, and MRR). We applied randomization tests to evaluate the statistical significance of the differences between run means as recommended in [START_REF] Smucker | A comparison of statistical significance tests for information retrieval evaluation[END_REF].

Concerning the Web2014 and Robust2004 collections, the qualified documents were the 50 top ranked documents returned using the Indri model, which was the model retrieving the most relevant documents for both collections. Similarly, the best feature per dataset was used to select the top 50 documents to be qualified in LETOR 3.0. Some other experiments were also run on all documents (up to 1000 per query) of the dataset; however, as these results were less significant, they will not be detailed here.

To answer Q1 we ran several experiments on the Web2014 and Robust2004 collections varying the set of features as described in the first line of Table 4. To fairly evaluate the impact of features, for each case (7 in total), 100 experiments were run randomly fixing all the other parameters among the values listed in Table 4 (lines 2 5).

The protocol used to answer Q2 is very similar: for each parameter we aimed to evaluate the behavior, i.e., the tournament type, the boosting technique, the impact (when a document loses on a feature the way its life gauge is decreased), and the strategy type (order by value, order by rank), we run 100 experiments randomly fixing the other parameters.

To answer Q3 and Q4, three variants of TOURNARANK were compared to state of the art approaches: two variants were chosen according to the results of Q1 and Q2, and one variant was issued from a 5 fold cross validation. More details about this cross