M.Sc Sébastien Roujol

PhD Baudouin Denis De Senneville

PhD Erkki Vahalla

Thomas Sangild Sorensen

PhD Chrit Moonen

PhD Mario Ries
email: mario.ries@imf.u-bordeaux2.fr

PhD Thomas Sangild Sørensen

Online real-time reconstruction of adaptive TSENSE with commodity CPU / GPU hardware

Keywords: Real-time reconstruction, TSENSE, Interventional Imaging. Word count: 3210

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Real-time MRI for therapy control is used to provide retroactive feedback information for interventional applications such as catheter guidance or MRI-controlled tissue ablation.

Such interventions require several minutes of continuous imaging and are preferably carried out under free-breathing conditions. This presents the following challenges to the MR-acquisition and reconstruction.

The data acquisition has to be rapid enough to resolve physiological motion such as respiratory or cardiac motion, and the signal changes from the interventional process itself. In addition, the employed data acquisition and reconstruction schemes must not introduce long image latencies, since this degrades the value of the image data for feedback control.

One of the significant developments in this field was the introduction of parallel imaging methods such as SMASH [START_REF] Sodickson | Simultaneous acquisition of spatial harmonics (SMASH): Fast imaging with radiofrequency coil arrays[END_REF], SENSE [START_REF] Pruessmann | SENSE: Sensitivity encoding for fast MRI[END_REF], or GRAPPA [START_REF] Griswold | Generalized autocalibrating partially parallel acquisitions (GRAPPA)[END_REF], which allows, on one hand, to accelerate the data acquisition and, on the other hand, to shorten readout echo-trains, and thus reduces signal dropout and image distortions in regions of large susceptibility variations. However, parallel imaging methods have also several drawbacks. SENSE, SMASH, and GRAPPA require coil sensitivity data for the image reconstruction, which depends on the coil position. Due to the long duration of interventional imaging procedures, displacements of the receiver coils are common and lead either to increased image artifacts over time, or, in the cases where the receiver coils are embedded in the interventional device itself, make these approaches altogether unsuitable. Several ideas have been brought forward to overcome this problem: AUTO-SMASH (4) embeds low-resolution k-space calibration data in the acquisition of undersampled high-resolution images. Alternative approaches, such as TSENSE [START_REF] Kellman | Adaptive Sensitivity Encoding Incorporating Temporal Filtering (TSENSE)[END_REF] or TGRAPPA [START_REF] Breuer | Dynamic autocalibrated parallel imaging using temporal GRAPPA (TGRAPPA)[END_REF], collect high-resolution calibration data at a lower temporal resolution than what is used for image encoding.Common to all of these techniques is the fact that the additional computational overhead leads to reconstruction times which often exceed the MR-acquisition time, in particular if large coil arrays are used, and are therefore in practice hard to exploit for real-time therapy guidance.

MATERIAL & METHODS

Reconstruction Architecture

A simplistic approach of the data handling and the reconstruction is illustrated in figure 1.a: upon completion of k-space sampling of the n th image, the data is transported from the acquisition system to the reconstruction system. There the reconstruction process is started and a new image acquisition can begin. Although this approach has the advantage of a straight forward implementation of the reconstructor pipeline due to its serial nature, it leads to a sub-stantial image latency. A more effective design to reduce image latency, which is to some extent standard on most commercially available MR-systems, is shown in figure 1.b. Here the acquired data of the n th image is transported to the reconstruction system line by line and the first preparative reconstruction steps are carried out immediately. Upon arrival of the last required k-space data, all remaining reconstruction steps are completed. Ideally, the data acquisition of the n+1 th image can be started as soon as the n th acquisition cycle is terminated. In practice, this leads to temporal overlap of data transport and image reconstruction. Further reduction of the image latency is achievable by reducing the computational time of the main reconstruction steps (as shown in figure 1.c) with a highly parallel reconstruction system such as a GPU.

The above means that for an efficient implementation, the MR-data have to be reorganized at several points during the reconstruction. Within the scope of this paper, the following reconstruction-related denotations apply: The MR-signal S is referred to as S(r,p,s,c). The order of the indices reflects the ordering of the data in the computer memory, r being the fastest varying component (r : index in read-out direction, p : index in phase direction, s : slice index, c : coil index). Let Nr, Np, Npsense, Ns and Nc define the number of elements in the read-out direction, the number of phase encoding steps, the number of phase encoding steps reduced by SENSE acceleration, the number of slices and the number of coils, respectively.

Reconstruction pipeline

The detailed overview of the implementation of a pipeline is shown in figure 2. The acquisition system streams raw k-space data of dynamic image n to a communication thread (CPU-thread #1) on the reconstructor, which feeds -over a buffer queue -a second preparatory reconstruction thread. Here k-space ordering and Fourier-reconstruction in readout-direction are carried out and the resulting x-ky-z-space is buffered to a shared-memory, which is accessible by all further reconstruction processes. The shared-memory is implemented as a round-robin to allow CPU-threads #3 and #4 to complete the reconstruction of dynamic image n, while threads #1 and #2 are immediately ready to receive and process new incoming data of the subsequent image n+1. The main image reconstruction is carried out by CPU-thread #3 which applies the EPI-phase corrections and Fourier transforms the image data in phase encoding direction.

For non-SENSE encoded images the image reconstruction would be complete at this point. SENSE encoded images require an additional unfolding step. Furthermore, adaptive TSENSE requires a continuous recalculation of the sensitivity maps and subsequently the SENSE matrix, which in itself is very time consuming. As Hansen et al. have shown, the highly linear nature of the reconstruction steps required for SENSE are well-suited for GPU offloading [START_REF]NVIDIA CUDA: Compute Unified Device Architecture -Programming Guide[END_REF]. The presented architecture takes advantage of the linearity by offloading all adaptive TSENSE calculations to a GPU. For this, the CPU-thread #4 sends a copy of the undersampled k-space to the GPU, which then partially updates a fully sampled k-space copy, as described by Kellman et al. [START_REF] Kellman | Adaptive Sensitivity Encoding Incorporating Temporal Filtering (TSENSE)[END_REF]. Subsequently, the GPU Fourier-transforms this data, calculates the corresponding sensitivity maps and recalculates the SENSE matrix.

Simultaneously, the CPU-thread #3 finalizes the Fourier-reconstruction of the folded image and sends the result to the GPU for the final SENSE reconstruction step.

Finally, an optional temporal filter used for residual artifact suppression can be applied. Upon completion of the reconstruction, the image is taken over by a CPU-thread #5 which dispatches the images to one (or several) viewing station(s).

GPU implementation

Since a detailed description of the GPU architecture can be found elsewhere [START_REF]NVIDIA CUDA: Compute Unified Device Architecture -Programming Guide[END_REF] and the potential of GPU-hardware for SENSE reconstruction has been evaluated by Hansen et al. [START_REF] Hansen | Cartesian SENSE and k-t SENSE Reconstruction using Commodity Graphics Hardware[END_REF], the description of GPU implementation is limited in the scope of this paper to the minimum required to understand the presented TSENSE implementation.

The employed GPU can be seen as a massively parallel coprocessor which contains 128 basic arithmetic processing units, which are, in turn, organized into teams of eight multiprocessors containing fast shared on-chip memory and a slower global memory shared across multiprocessors. The CUDA programming API (8) of the GPU reflects this architecture in the following way: executable code is broken down into a sequentially executed set of kernels, which are organized into a grid of Nblock blocks. Each block contains a set of Nthread threads executed in parallel by one multiprocessor.

Data is exchanged between the dynamic random access memory (DRAM) of the GPU and the RAM of the hosting computer via direct memory access (DMA) of the PCI-express bus, which is bandwidth limited to 3-4 GB/s. In addition the GPU DRAM memory access has a high latency (400-600 clock cycles). Therefore, in order to obtain a maximal processing performance on this particular GPU architecture, the TSENSE method was implemented according to the following guidelines:

 Excessive exchange of data between the RAM of the hosting computer and the GPU has to be avoided.

 The large memory latency of the global GPU DRAM can be hidden by designing the kernels to solve the mathematical problems with a high density of arithmetic operations per memory access and designing the execution configuration to exploit the dimensionality of the given problem to maximize Nblock and Nthread.

 Memory intensive processing has to be implemented so that cooperation takes place between threads within the same block and not between different blocks.

 Multi-dimensional data in the DRAM should be organized so that memory access from the individual threads results in contiguous memory access by the memory controller.

Fourier Reconstruction in phase encoding direction

Since for the most of the GPU reconstruction steps Nblock=Nr, and Nthread=Np, the data is first reordered from data organisation S(r,p,c,s) to S(p,r,c,s) to allow coalesced memory access by the threads (Nthread=16×16 in our implementation, Nblock=NrNpNcNs/Nthread). This step also prepares the Fast Fourier Transformations (FFTs) in phase encoding direction by applying the required frequency shifts. Subsequently, the CUDA programming API (8) provided FFT is applied in the p-dimension (using Nthread=Np, Nblock=NrNcNs,), resulting in an unaliased image for each receiver coil and slice.

Sensivity Map Update

First, the calculation of the synthetic reference image is performed. This can be, for the case of TSENSE, provided by the Sum-of-Square of the coil images (2) (Nthread=Np, Nblock=NrNs). Subsequently, the coil sensitivities are calculated (Nthread=Np, Nblock=NrNs) and optionally, a receiver coil noise decorrelation step (10) is performed. For the decorrelation step, the first Nc threads load each one element of the pre-calculated noise-decorrelation matrix ψnoise -1 Id. After a mutual barrier point each thread loads the reference image value for the position associated with the thread and calculates the spatial coil sensitivity map S for all coils.

The noise decorrelated sensitivity maps Sdecorr are obtained as follows:

Sdecorr=(ψnoise -1 Id)S [1]
The result is stored in S(c,p,r,s) order to prepare the SENSE-matrix recalculation.

Temporal Filtering

For residual artifact suppression, all sensitivity maps are temporally filtered with an infinite impulse response filter (IIR) (Nthread=Np, Nblock=NrNcNs) using a SENSE factor dependent bandwidth of 1/SENSE_factor as described in detail by Maclair et al. (11).

SENSE-matrix Recalculation

The unfolding matrix U is calculated for each slice position (using Nthread=Nr, Nblock=NpNs /SENSE_factor) as follows:

U=(Sdecorr H Sdecorr) -1 Sdecorr H [2]
Each thread calculates the matrix inversion for one pixel using an adapted version of the LU-decomposition algorithm (12). Alternatively, for larger coil arrays, a Cholesky (12) decomposition can be used.

SENSE-Reconstruction

This step (performed using Nthread=Npsense, Nblock=NrNs) begins optionally with a noisedecorrelation of folded image. For this, the same process as the one used in sensitivity map noise-decorrelation (see equation [START_REF] Sodickson | Simultaneous acquisition of spatial harmonics (SMASH): Fast imaging with radiofrequency coil arrays[END_REF]) is applied. Then, the unfolding process is performed as follows:

Iunaliased=U.Ialiased [START_REF] Griswold | Generalized autocalibrating partially parallel acquisitions (GRAPPA)[END_REF] where Iunaliased and Ialiased are the unaliased and the aliased image, respectively. Note that superimposed voxel indices are precalculated in both data organisations S(r,p,c,s) and S(p,r,c,s) to speed up this step. In our implementation, Ialiased is computed on the CPU in parallel with the SENSE-matrix recalculation step explained above.

MRI

All in-vivo experiments were performed on a Philips Achieva 3.0 T X-series scanner equipped with a Philips 16-channel torso coil, using a gradient-echo EPI (GE-EPI) sequence.

The following acquisition parameters were used:

Abdominal thermometry imaging:

A single slice placed on the right kidney of a healthy volunteer was acquired using an echotrain of 67 echoes (33 for two-fold and 17 for four-fold acceleration, respectively), a fixed TE of 15 ms and TR of 50 ms for all acceleration factors, a flip angle of 35 º, a bandwidth in phase-encoding direction BWpe of 4.1 kHz (1.5 kHz for two-fold and 0.7 kHz for four-fold acceleration), and a resolution of 3.13×3.13×5 mm 3 . Fat suppression with spectral pre-saturation with inversion recovery (SPIR) was used.

Cardiac imaging:

A single slice placed on the right ventricular outflow tract and the aorta of a healthy volunteer was imaged using an echo-train of 63 echoes (31 for SENSE 2; 15 for SENSE 4), a TR of 50 ms, a TE of 15 ms (7.8 ms for SENSE 2, 4.5 ms for SENSE 4), a flip angle of 35 º, a

BWpe=3.9 kHz and an image resolution of 3.0×3.0×5 mm 3 .

Reconstructor Hardware

The reconstructor was a dual processor (INTEL 3.1 GHz Penryn, four cores) workstation with 8 GB of RAM and dual 1 Gb/s network interface cards. The GPU was a NVIDIA 8800GTX card with 768 MB of DRAM connected over a PCIe x16 link.

Reconstructor Software

The reconstructor was running under Linux (SMP-Kernel 2.6.18) which was stripped from all non-essential system processes. For the data transport from the MR-acquisition system to the reconstructor and from the reconstructor to the viewing station(s) a real-time implementation of the common object request broker architecture (CORBA) known as The Ace Orb (TAO) (13,14) was used. For Fourier reconstruction and all linear algebra operations on the CPU, the ACML math package (15) was employed. The package contains linear algebra packages BLAS (16) and LAPACK (17). The GPU implementation of the adaptive TSENSE method was realized using CUDA [START_REF]NVIDIA CUDA: Compute Unified Device Architecture -Programming Guide[END_REF], with in-house developed linear algebra routines based on methods presented in Numerical Recipes in C++ (18).

RESULTS

Detailed performance comparison between the CPU only and the CPU/GPU implementation

Table 1 compares the computation time for each TSENSE reconstruction step for a two-fold accelerated image (resolution 128×128, six receiver channels) between the implementation using the CPU only and the CPU/GPU implementation. The two most time consuming tasks, the temporal filtering of sensitivity maps and the SENSE matrix recalculation, were accelerated by a factor of 14.7 and 16.3, respectively and lead to an overall eight-fold increase of the reconstruction speed despite the additional data transfer to the GPU.

Real-time benchmarking of throughput and latency

Table 2 reports the data transfer time, the reconstruction time and the resulting image latency (as defined in figure 1) under real-time conditions for coil setups with 4, 6, 8, and 16 elements, and TSENSE acceleration factors of 2, 3, and 4 (resolution 128×128, two-fold readout oversampling). Since computation times for multi-slice acquisitions are almost linear with the slice number, only results measured with a single slice are reported.

Data transport varies between 17 ms (four-fold accelerated, four channels, ~135 kB per image) to 76 ms (two-fold accelerated, 16 channels, ~1 MB per image) depending on the data size. The reconstruction itself has a theoretical peak performance between 75 images/s (SENSE 4, 16-channels) to 330 images/s (SENSE 2, 4-channels). However, in practice the achievable peak data-throughput was found to be limited by the I/O subsystem of the acquisition system to ~2.1 MB/s, which corresponds to an image frame-rate of 20 images/s for a two-fold TSENSE accelerated data set (128×128, two-fold read-out oversampling, 16 receiver channels) with a overall image latency of 90 ms, or 40 images/s and an image latency of 60 ms for a four-fold acceleration. outflow tract and the aorta as it would typically be used for catheterization guidance, obtained with 20 images/s. Besides the residual folding artifacts in areas of limited coil coverage, the target area was found to be artifact-free during the entire experiment.

In-vivo imaging

DISCUSSION

The usefulness of a reconstruction pipeline for real-time MR-guidance of interventional procedures can be characterized by the reconstruction speed and the achievable image latency. Fundamentally, the reconstruction time of the pipeline has to be comparable to, or preferably shorter as, the acquisition time of the MR-system, in order to maintain the realtime condition for sustained imaging. Table 2 shows that a purely CPU-based reconstruction limits MR-acquisition to only 4-6 coils elements and SENSE acceleration factor to 2-3. Since the proposed CPU/GPU implementation of the TSENSE reconstruction achieves in average an eight-fold acceleration, these limits are virtually removed. In practice, this means that imaging speed is now limited by the boundaries imposed by the MR-sequence, the specific absorption rate, the desired signal-to-noise ratio and the I/O-bandwidth of the acquisition system.

For the case of MR-guided surgical interventions, large image latencies introduce a significant lag between the action and its observable consequence and thus limit the accuracy and speed of the procedure. The proposed CPU/GPU reconstruction achieves image latencies from 20 to 90 ms for all coil configurations and acceleration factors, and is thus well-suited for manual feedback.

For the case of MR-image guidance of semi-or fully-automated interventions, such as high intensity focused ultrasound (HIFU) ablations, short latencies are of even greater importance. In this type of application, the position and target temperature are ascertained with the help of MR-imaging/thermometry and further used to retroactively adjust the beam

  Guttman et al. demonstrated the feasibility of a real-time reconstruction for adaptive TSENSE on a four channel receiver system with an image latency of ~0.3 s (7). Recently, Hansen et al. showed that a Cartesian SENSE reconstruction can be significantly acceleratedby up to two orders of magnitude -if the massively parallel architecture of commodity graphics hardware (GPU) is used (8). The presented work combines both approaches to demonstrate the ability to reconstruct adaptive TSENSE data in real-time with low image latencies on affordable commodity hardware. For this, a detailed performance comparison of the TSENSE reconstruction steps for the GPU and CPU implementation is presented and the image latency and throughput of the full reconstruction under different typical interventional work-loads are benchmarked. Finally, the benefit of the proposed online reconstruction for therapy guidance is demonstrated with two in-vivo imaging experiments imitating conditions typical for MR-guided thermotherapy on abdominal regions and cardiovascular catheterization under real-time MRI guidance.

Figure 3

 3 Figure 3 compares the computation time measured for various TSENSE acceleration factors (2, 3 and 4) and different image resolutions (128×128, 256×256 and 512×512 pixels)

Figures 4

 4 Figures 4 shows a fully sampled (a), two-fold accelerated (b) and four-fold accelerated (c) abdominal image of the right kidney of a healthy volunteer obtained under free-breathing conditions. An imaging frame-rate of 20 images/s was maintained online for 300 seconds of MR-imaging. The thorax and the lower abdomen show residual folding artifacts due to limited coil coverage. The center of the image depicting the kidney was artifact-free over the entire imaging duration and is hence suitable for continuous MR-thermometry. Similarly, figures 4.d, 4.e, and 4.f show a cross-section through the right ventricular

FIGURE CAPTIONS Figure 1 .

 CAPTIONS1 FIGURE CAPTIONS

Figure 2 .

 2 Figure 2. Overview of the thread architecture of the reconstruction pipeline.In order to achieve high throughput and short image latencies, as many independent data handling/reconstruction steps as possible are carried out in parallel: CPU-threads one and two handle/reconstruct k-space data from the dynamic image n+1, while CPU-threads three and four finalize simultaneously the reconstruction of dynamic image n. The time-consuming processing steps for the adaptive TSENSE reconstruction are offloaded to GPU-hardware which in itself uses up to 128 threads in parallel. A separate thread for dispatching the data to a visualization and an archiving system is used.

Figure 3 .

 3 Figure 3. Computation time measured for various TSENSE acceleration factors (2, 3 and 4) and different image resolutions (128×128, 256×256 and 512×512 pixels) using the CPU only (a) and using the CPU/GPU approach (b). Acceleration factors around 7-8 were measured with the proposed CPU/GPU approach for each tested resolution. Computation times remain identical using the proposed CPU/GPU approach for each tested TSENSE acceleration factor.

Figure 4 .

 4 Figure 4. Real-time reconstructed MR-images using a combined CPU/GPU reconstruction (left-right: foot-head, up-down: anterior-posterior direction): (a-c) : Fully sampled abdominal image centered on the kidney (a) and TSENSE accelerated by factor of 2 (b) and 4 (c). (d-f) : Right ventricular outflow tract and the aorta, with full sampling (d) and with a TSENSE acceleration factor of 2 (e) and 4 (f).

TABLE CAPTIONS Table 1 .

 CAPTIONS1 Computation time for all TSENSE reconstruction steps for a single slice of resolution 128×128 pixels with an acceleration factor of 2 using six receiver coils.

Table 2 .

 2 Reconstruction time and image latency for a single slice reconstruction of resolution

	128×128 with TSENSE factor 2, 3, 4 for 4, 6, 8, 16 coil channels. With the proposed
	CPU/GPU implementation, total computation times are far below the TR on all tests
	demonstrating that real-time reconstruction is feasible.


Julien Ah-Pine
email: julien.ah-pine@fr.thalesgroup.com

Jean-François Marcotorchino
email: jeanfrancois.marcotorchino@fr.thalesgroup.com

Belson

Julien Ah
email: julien.ah-pine@xrce.xerox.com

Statistical, geometrical and logical independences between categorical variables

Keywords: Relational Analysis, Association criteria, Independences, Nominal categorical variables

Classical association criteria, used for measuring statistical independence between categorical variables, are initially defined using contingency tables. There is another way for representing categorical variables : Relational Analysis which uses binary pairwise comparison matrices formalism. There exists correspondance formulas that enable to get from one representation to the other. By using these formulas, and these two representations, we can have a better understanding of the main differences between some famous association criteria. In fact, several types of independence, namely statistical, geometrical and logical, appear using one representation or the other. The aim of this paper is to present in a unified framework, these different kinds of independence and their relationships by studying the expression of the following association criteria in the two different representations :

Relational Analysis (RA) is concerned with the analysis of binary relations and their applications in different mathematical fields [Marcotorchino, 2006]. This approach represents the binary relations as pairwise comparison matrices, and it is basically related to different tools from graph theory, statistics and linear programming. The most usual application domains of RA are data analysis and multicriteria decision making which are respectively based upon the aggregation of equivalence and order relations.

Here, we are particularly interested in the applications of RA in the analysis of association criteria. Previous work has been done in this area and different association criteria have been partially unified under the concept of geometrical independence using RA [Marcotorchino, 1984], [Najah Idrissi, 2000]. Our aim is to recall these results and to go further by adding other association criteria and by underlying another independence concept, called indetermination which is based on a logical approach [Marcotorchino, 1984].

From contingency representation to relational representation

We assume that we have N objects, {O i ; i = 1, . . . , N }. For these objects, let V k and V l be two nominal categorical variables with respectively p k and p l classes. The sets of classes will be denoted by {D k u ; u = 1, . . . , p k } and {D l v ; v = 1, . . . , p l }. One can represent each of these variables by binary assignment matrices. For example in the case of V k , we have the following (N × p k ) matrix :

K k iu = 1 if O i belongs to the class D k u 0 else
From K k and K l , we can deduce the following contingency table denoted by n kl with dimensions (p k × p l ) :

n kl = t K k • K l
where t K k is the transpose matrix associated to K k and • the matrix multiplication.

We have the following notations and interpretations, ∀u = 1, . . . , p k and ∀v = 1, . . . , p l :

• n kl uv =Number of objects belonging both to the class

D k u of V k and D l v of V l • p l v=1 n kl uv = n kl u. =Number of objects belonging to the class D k u of V k • p k u=1 n kl uv = n kl .v =Number of objects belonging to the class D l v of V l • p k u=1 p l v=1 n kl uv = N = Total number of objects
We will study the following association criteria : Belson (B), Lerman (L), χ 2 of Tchuprow (T ), Jordan (J), Rand (R), and Janson-Vegelius (JV ). These criteria are initially defined using the contingency table. We recall their definitions. We precise that the Rand and the Lerman criterion we mention, is a modified version according to [Marcotorchino, 1984] and [Najah Idrissi, 2000].

B(V k , V l ) = p k u=1 p l v=1 n kl uv - n kl u. n kl .v N 2 L(V k , V l ) = u,v (n kl uv ) 2 - u (n kl u. ) 2 v (n kl .v ) 2 N 2 u (n kl u. ) 2 1- u (n kl u. ) 2 N 2 v (n kl .v ) 2 1- v (n kl .v ) 2 N 2 T (V k , V l ) = u,v 1 n kl u. n kl .v n kl uv - n kl u. n kl .v N 2 √ (p k -1)(p l -1) J(V k , V l ) = 1 N u,v n kl uv n kl uv - n kl u. n kl .v N R(V k , V l ) = 2 u,v (n kl uv ) 2 - u (n kl u. ) 2 - v (n kl .v ) 2 +N 2 N 2 JV (V k , V l ) = p k p l u,v (n kl uv ) 2 -p k u (n kl u. ) 2 -p l v (n kl .v ) 2 +N 2 (pk(pk-2) u (n kl ) 2 u. +N 2 )(pl(pl-2) u (n kl .v ) 2 +N 2 )
We also have the following expression for the Janson-Vegelius criterion :

JV (V k , V l ) = p k p l u,v n kl uv - n kl u. p l + n kl .v p k -N p k p l 2 (pk(pk-2) u n 2 u. +N 2 )(pl(pl-2) u n 2 .v +N 2 )
RA is another way of representing nominal categorical variables. This representation uses pairwise comparison matrices.

Let C k and C l be the relational matrices of dimension (N × N ), representing the variables V k and V l . We can obtain C k and C l by using the matrices K k and K l :

C k = K k • t K k and C l = K l • t K l
In general terms, let R be a binary relation among a set of N objects O 1 , . . . , O N . If C is the relational matrix for R then we have, ∀i, i = 1, . . . , N :

C ii = 1 if O i is in relation with O i 0 else
In our context, the studied binary relations are equivalence relations (or partitions) and we have for V k :

C k ii = 1 if O i and O i belong to the same class according to V k 0 else
Following Kendall [Kendall, 1970], Marcotorchino has developped correspondance formulas between contingency and relational representations. Using these correspondance formulas we can express the mentionned association criteria using the relational coding [Marcotorchino, 1984].

We give in Table 1 the classical correspondance formulas [Marcotorchino, 1984].

Contingency ↔ Relational representation representation p k u=1 p l v=1 (n kl uv ) 2 = N i=1 N i =1 C k ii C l ii u (n kl u. ) 2 = i,i C k ii v (n kl .v ) 2 = i,i C l ii u,v (n kl uv ) 2 n kl u. n kl .v = i,i C k ii C l ii C k i. C l i. u,v n kl uv n kl u. n kl .v = i,i C k i. +C k .i 2 C l ii u,v (n kl uv ) 2 n kl u. = i,i C k i. +C k .i 2 C k ii C l ii u,v (n kl uv ) 2 n kl u. = i,i C k ij C k i. C l ii v u n kl u. n kl uv 2 = i,i C k i. C k .i C l ii u,v (n kl u. ) 2 (n kl .v ) 2 = N i,i C k .. C l ii where n kl u. = v n kl uv and C k i. = i C k ii Table 1. Correspondance

formulas between contingency representation and relational representation

In [Najah Idrissi, 2000], it is given the symmetric relational expression for Rand, Janson-Vegelius, Lerman, and Tchuprow criteria. We extend these results by giving the symmetric expression of Belson and Jordan criteria.

B(C k , C l ) = N i=1 N i =1 C k ii - C k i. +C k .i N + C k .. N 2 C l ii - C l i. +C l .i N + C l .. N 2 L(C k , C l ) = i,i C k ii - i,i C k ii N 2 C l ii - i,i C l ii N 2 i,i C k ii - i,i C k ii N 2 2 i,i C l ii - i,i C l ii N 2 2 T (C k , C l ) = i,i C k ii C k i.
-

1 N C l ii C l i.
-

1 N i,i C k ii C k i.
-

1 N 2 i,i C l ii C l i.
-

1 N 2 J(C k , C l ) = 1 N i,i C k ii - C k i. N C l ii - C l i. N R(C k , C l ) = 1 N 2 i,i C k ii C l ii + C k ii C l ii JV (C k , C l ) = i,i C k ii -1 p k C l ii -1 p l i,i C k ii -1 p k 2 i,i C l ii -1 p l 2 where C k ii = 1 -C k ii , C k = U N -C k and U N is the (N × N ) square matrix
where all terms equal 1.

We also have the following equation for the Rand criterion :

2R(C k , C l ) -1 = i,i (C k ii -1 2 )(C l ii -1 2 ) i,i (C k ii -1 2 ) 2 i,i (C l ii -1 2 )
2 2 From statistical independence to geometrical independence

We say that two nominal categorical variables V k and V l are statistically independent if their joint probabilities,

n kl uv N
, equal the product of their marginal probabilities,

n kl u. N n kl .v N : V k ⊥ S V l ⇔ n kl uv N = n kl u. N n kl .v N ∀(D k u , D l v ) : D k u ∈ V k , D l v ∈ V l (1)
According to this principle, we can measure the association (or the relationship) between two nominal categorical variables by measuring their de-viation from the statistical independence situation. In the contingency representation, many of the presented association criteria are based upon this approach. Indeed, we clearly see, that the Belson, the Lerman, the Tchuprow and the Jordan criteria are null if V k and V l are statistically independent.

In the relational representation, we can interpret each relational matrix as a binary tensor in a tensor space of canonical basis {e i ⊗ t e i ; i, i = 1, . . . , N } where e i is the canonical vector and ⊗ the Kronecker product.

Consequently, we can interpret the association criteria expressed in their relational representation, from a geometrical point of view.

More precisely, let C k , C l F be the Frobenius scalar product derived from the Frobenius norm of a matrix. We have :

C k , C l F = N i=1 N i =1 C k ii C l ii = Trace( t C k • C l )
We can show that, using the relational coding, one can express the main different association criteria that we have recalled, as particular cases of a general Bravais-Pearson like correlation coefficient between relational matrices [Marcotorchino, 1984], [START_REF] Marcotorchino | [END_REF], [Najah Idrissi, 2000] :

∆(C k , C l , f, µ k , µ l ) = i,i (f(C k ii )-µ k )(f(C l ii )-µ l ) i,i (f(C k ii )-µ k ) 2 i,i (f(C l ii )-µ l ) 2 = f (C k )-µ k U N ,f (C l )-µ l U N F √ f (C k )-µ k U N ,f (C k )-µ k U N F f (C l )-µ l U N ,f (C l )-µ l U N F
(2) According to (2), we can see that the differences between the criteria are based upon :

• the transformation function f applied to the terms of the relational matrices • the central trends µ k and µ l , which are given parameters We give in Table 2, the different values of the parameters (f, µ k , µ l ), which define a particular coefficient. These different coefficients are related to the mentionned association criteria.

Accordingly, we say that two nominal categorical variables are geometrically independent if we have the following relation :

V k ⊥ G V l ⇔ ∆(C k , C l , f, µ k , µ l ) = 0 ⇔ i,i f (C k ii ) -µ k f (C l ii ) -µ l = 0 (3)
The RA approach has enabled to get a better understanding of the main differences between the presented association criteria. We have seen that there exists a particular relationship between contingency representation /

f (C ii ) µ k µ l Related criteria Relation with the related criteria f (C ii ) 0 0 Belson The Belson criteria = is the numerator C ii - C i. +C .i N + C.. N 2
of the defined Torgerson transf. coefficient

f (C ii ) = C ii C k .. /N 2 C l .. /N 2 Lerman L(C k , C l ) f (C ii ) = C ii /Ci. 1/N 1/N Tchuprow T (C k , C l ) f (C ii ) = C ii C k i. /N C l i. /N Jordan The Jordan criteria is the numerator of the defined coefficient ×1/N f (C ii ) = C ii 1/2 1/2 Rand 2R(C k , C l ) -1 f (C ii ) = C ii 1/p k 1/p l Janson- JV (C k , C l ) Vegelius
Table 2. Correspondance between correlation coefficient and association criteria statistical independence and relational representation / geometrical independence.

We give in the following, two other results that strengthen this duality between the contingency and the relational representations. Firstly, we show the link between the modified Lerman criterion and the tetrachoric correlation coefficient. Secondly, we establish a specific statistical / geometrical independence duality between the Belson criterion and the Janson-Vegelius (its numerator) criterion.

In the relational representation, the nominal categorical variables through their relational matrices C k and C l , can be interpreted as 0/1 variables. As a result, we can consider the (2 × 2) table given in Table 3.

C l C l Margin C k 11 kl = i,i C k ii C l ii 10 kl = i,i C k ii C l ii i,i C k ii C k 01 kl = i,i C k ii C l ii 00 kl = i,i C k ii C l ii i,i C k ii Margin i,i C l ii i,i C l ii N 2
Table 3. Agreements and disagreements between relational matrices

Considering Table 3, we can express the statistical independence concept by using another measure called the odds-ratio (OR). Then, we also say that two nominal categorical variables are statistically independent if we have the following relation :

V k ⊥ S V l ⇔ OR(C k , C l ) = 11 kl 00 kl /10 kl 01 kl = 1
⇔ 11 kl 00 kl -10 kl 01 kl = 0 (4) Indeed, using the correspondance formulas we can show that :

11 kl 00 kl -10 kl 01 kl = u,v (n kl uv ) 2 -u (n kl u. ) 2 v (n kl .v ) 2 N 2 = i,i C k ii -i,i C k ii N 2 C l ii -i,i C l ii N 2
Actually, we have the following identity :

L(C k , C l ) = Tetrachoric(C k , C l ) = 11 kl 00 kl -10 kl 01 kl √ (11 kl +10 kl )(01 kl +00 kl )(11 kl +01 kl )(10 kl +00 kl )
We consider now the Belson criterion and the Janson-Vegelius criterion's numerator. We establish a particular relationship between these two criteria : on the one hand the Belson criterion, in its contingency representation, is based on the statistical independence and in the relational presentation, it is based on a geometrical independence associated to the Torgerson 1 transformation; on the other hand, the Janson-Vegelius criterion's numerator, in its

1 C k ii - C k i. +C k .i N + C k .. N 2 = O i k -G k , O i k -G k . {O i k ; i = 1, . . . , N } are (p k × 1) binary vectors where [O i k ]u = K k iu ; u = 1, . . . , p k and G k = N i=1 O i k
contingency representation, is based on the geometrical independence associated to the Torgerson transformation, and in the relational representation it is based on the statistical independence upon equiprobability assumption.

We represent this relationship in Table 4.

Deviation from Geometrical independence statistical independence based on Torgerson transformation

Belson u,v n kl uv - Firstly, considering the Janson-Vegelius criterion's relational representation, we can interpret the term (C k ii -1 p k ), as a deviation from statistical independence in an equiprobability context. Let P (C k ii ) be, symbolically, the probability for two objects O i and O i , belonging to the same class of V k . Let assume moreover, that the different classes D k u ; u = 1, . . . , p k ; are equiprobable. This involves that the probability for an object to belong to any class of V k equals 1/p k . Then, in case of probability independence, we have :

n kl u. n kl .v N 2 i,i C k ii - C k i. N + C k .i N - C k .. N 2 C l ii - C l i. N + C l .i N - C l .. N 2 Janson-Vegelius i,i C k ii -1 p k C l ii -1 p l u,v n kl uv - n kl u. p l + n kl .v p k - n kl .. p k p l 2 (numerator)
P (C k ii ) = p k u=1 P ("O i and O i belong to the class D k u ") = p k u=1 P ("O i belongs to the class D k u ")P ("O i belongs to the class D k u ") = p k u=1 1 p k 1 p k = 1 p k
Secondly, considering the Janson-Vegelius criterion's contingency presentation, we can interpret the term (n kl uv -

n kl u. p l + n kl .v p k - n kl ..
n kl uv - n kl u. p l - n kl .v p k + n kl .. p k p l = D k u -G k , D l v -G l ∀(D k u , D l v ) ∈ V k × V l where G k = 1 p k D k u ∈V k D k u and G l = 1 p l D l v ∈V l D l v .
3 A logical independence approach called "indetermination"

Among the previous studied association criteria, the one which is related to the Rand criterion and given by the paramaters (f = Id, µ k = 1/2, µ l = 1/2), is a special case. Although it has through its relational coding, an interpretation based on the geometrical independence, we can also interpret it using a logical approach which is called indetermination [Marcotorchino, 1984]. We say that two nominal categorical variables are indetermined or logically independent if we have the following relation :

V k ⊥ L V l ⇔ 11 kl + 00 kl -10 kl -01 kl = 0 ⇔ i,i C k ii C l ii + i,i C k ii C l ii -i,i C k ii C l ii -i,i C k ii C l ii = 0 ⇔ i,i C k ii -C k ii C l ii -C l ii = 0 ⇔ 4 i,i C k ii -1/2 C l ii -1/2 = 0
(5) This corresponds to the situation where, for two nominal categorical variables, the number of agreements given by 11 kl + 00 kl is the same as the number of disagreements given by 10 kl + 01 kl . The statistical independence defined by ( 4) is a multiplicative model associated to the number of agreements and disagreements. On the contrary, the indetermination or logical independence defined by (5), is an additive model which is a different way of measuring the association between two nominal categorical variables.

The indetermination concept can also be extended by giving weightings to agreements and disagreements :

V k ⊥ L V l ⇔ µ k 1 µ l 1 11 kl + µ k 0 µ k 0 00 kl -µ k 1 µ l 0 10 kl -µ k 0 µ l 1 01 kl = 0 (6)
We will consider the following general formula which gives a normalized coefficient that measures the deviation from the indetermination's situation between two categorical variables. This coefficient denoted Λ is null in the case of indetermination :

Λ(C k , C l , µ k 1 , µ k 0 , µ l 1 , µ l 0 ) = i,i µ k 1 C k ii -µ k 0 C k ii µ l 1 C l ii -µ l 0 C l ii i,i µ k 1 C k ii -µ k 0 C k ii 2 i,i µ l 1 C l ii -µ l 0 C l ii 2 (7)

p

  k p l ), as the Torgerson transformation of the (N × 1) binary vectors {D k u ; u = 1, . . . , p k } and {D l v ; v = 1, . . . , p l } where [D k u ] i = K k iu ; i = 1, . . . , N . Indeed, we have n kl uv = D k u , D l v and the following relation :

Table 4 .

 4 Dual relationship between Belson and Janson-Vegelius criteria due to the contingency / relational presentation duality

Finally, we give the relation below which shows the formal link between geometrical independence and indetermination in the relational representation :

For example, when

Finally, we have seen that using one representation or the other, we can have different concepts of independence for measuring the relationship between two categorical variables. It is important to have a good understanding of the differences between association criteria that are proposed in the litterature. RA has enabled to contribute to this issue by showing the relationship between contingency representation / statistical independence and relational representation / geometrical independence. But RA enables to go further by pointing out another kind of independence concept : indetermination between two categorical variables. This approach, that is inherent to the Rand 2 criterion, has a logical definition and can be interpreted as a voting rule. Furthermore, the RA method has enabled to define partitioning criteria using association criteria. This was defined by Marcotorchino, as the maximal association model for the clustering problem [Marcotorchino, 1986a], [Marcotorchino, 1986b].


Julien Ah-Pine
email: julien.ah-pine@xrce.xerox.com

Data fusion in information retrieval using consensus aggregation operators

In this paper, we address the problem of unsupervised rank aggregation in the context of meta-searching in information retrieval field. The first goal of this paper is to apply aggregation operators that are defined in information fusion domain to the particular issue mentioned beforehand. Triangular norms, conorms and quasi-arithmetic means, are such kind of operators. Then, the second goal of this work is to introduce a new aggregation function, its logical foundations and its combinatorial properties. Particularly, this operator allows to take into account the relationships between experts in a flexible way. Finally, we test these different aggregation operators on the LETOR dataset. The results of our experiments show that this kind of aggregation functions can lead to better results than baseline methods such as CombSUM and CombMNZ approaches.

Introduction

Data fusion problems arise when for a given task, there are several experts which give different opinions. These opinions can agree or not and we are faced with the problem of combining them in order to figure out a consensus decision. That kind of issue can be encountered in different contexts: in voting theory, we have to aggregate the votes or preferences of many individuals in order to elect a consensus candidate; in decision making we have several alternatives and we have to choose the most appropriate one according to several criteria. Aggregating preference relations is an issue that has been analyzed in social sciences [START_REF] Condorcet | Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix[END_REF], [START_REF] Arrow | Choix collectif et préférences individuelles[END_REF], [START_REF] Fishburn | Mathematics of decision theory[END_REF] and in statistics [START_REF] Kendall | Rank correlation methods[END_REF], [START_REF] Marcotorchino | Optimisation en analyse ordinale des données[END_REF].

More recently, in information retrieval, tasks such as meta-search problems aim at combining the results given by different search engines into a single consensus list of web pages which is expected to be more robust and efficient than if we take into account only one search engine.

In this paper, we are concerned with the data fusion problem when the experts' opinions are ranking distributions (rank values or score values) over a set of objects. We are more particularly interested in addressing this issue in the context of information retrieval. In this situation, there are several specificities which are analyzed in [START_REF] Farah | An outranking approach for rank aggregation in information retrieval[END_REF]. For example, in information retrieval, unlike in multicriteria decision making, we rather aggregate partial lists and the number of partial rankings (the number of search engines) to be combined is lower than the number of objects.

In the information retrieval community, many methods have been proposed for "learning to rank" in order to tackle rank aggregation problems in a supervised manner. In our case, we assume that there is no training data available and we rather deal with unsupervised rank aggregation issues.

In that context, linear combination of experts' scores such as CombSUM or CombMNZ methods [START_REF] Fox | Combination of multiple searches[END_REF], often give robust results. A recent work detailed in [START_REF] Farah | An outranking approach for rank aggregation in information retrieval[END_REF] proposes to extend aggregation approaches developed in multicriteria decision making field for dealing with rank aggregation problems in information retrieval. One of the aims of the present work is similar to the one presented in this last paper: we want to apply aggregation operators already defined in other fields (information fusion field in our case [START_REF] Bloch | Information Combination Operators for Data Fusion: A Comparative Review with Classification (invited conference)[END_REF], [START_REF] Meunier | Aggregation and fusion of imperfect information[END_REF]), to the rank aggregation problem in information retrieval. The paper is organized as follows.

In section 2, we first recall some related works and we introduce the basic notations and the baseline approaches CombSUM and CombMNZ. Second, in section 3, we give some details about the scores' normalization step that is required when applying aggregation functions. Next, in section 4, we recall some well-known aggregation operators in information fusion field: triangular norms, triangular conorms and quasi-arithmetic means. Another goal of this paper is then to introduce, in section 5, a new consensus aggregation function. This method has logical foundations, it involves triangular norms and more generally conjunction operators. As we will see, despite its combinatorial aspect, we prove a property that allows to reduce the computational cost of this new function. Finally, we experiment the different proposals using three datasets taken from the LETOR package [START_REF] Liu | Letor: Benchmark dataset for research on learning to rank for information retrieval[END_REF]. The experiments results given in section 6, show that many aggregation functions and particularly, our method, give better results than baseline approaches.

Related work and notations

We suppose there are M experts (the search engines) and N objects. Each expert gives an ordered list of those N objects according to their own preferences (or scores). However, we will restrict ourselves to the top list of each expert (partial rankings). In other words, we don't consider the whole list but only the most relevant objects according to each expert. From these M ordered top lists, the problem we address is to find a single consensus list which combines the M rankings. There are different methods for addressing this issue and we can in fact, notice two families of approaches according to [START_REF] Riker | Liberalism against populism[END_REF], [START_REF] Farah | An outranking approach for rank aggregation in information retrieval[END_REF]:

• positional methods: for each object, we consider the scores given by each expert (the object's profile), we then aggregate these scores using different techniques and we finally re-rank the objects using the aggregated scores. The first positional method was proposed by Borda [START_REF] Borda | Mémoire sur les élections au scrutin[END_REF] but linear combination such as the arithmetic mean is for instance, one of these methods [START_REF] Fox | Combination of multiple searches[END_REF].

• majoritarian methods: these methods use pairwise comparisons matrices of objects and are mostly based upon order relations aggregation using association criteria such as Condorcet's criterion [START_REF] Condorcet | Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix[END_REF], [START_REF] Michaud | Modèles d'optimisation en analyse des données relationnelles[END_REF] or distance criteria such as Kendall distance [START_REF] Marcotorchino | Optimisation en analyse ordinale des données[END_REF], [START_REF] Fagin | Comparing top k lists[END_REF]. Other methods have also been proposed using Markov chain models [START_REF] Dwork | Rank aggregation methods for the web[END_REF]. Lastly, outranking methods which were introduced in multicriteria decision problems have been adapted for information retrieval tasks [START_REF] Roy | The outranking approach and the foundations of ELECTRE methods[END_REF], [START_REF] Farah | An outranking approach for rank aggregation in information retrieval[END_REF].

The methods proposed in this paper belong to the positional family. Before introducing the most popular approaches used in this context, we first give some basic notations:

• S j (i) is the normalized score expert j assigns to object i.

• L(j) is the ordered list of expert j.

• L k (j) is the first k objects of L(j) or the top-k list of expert j. We will also denote L k = {L k (j); j = 1, . . . , M } the set of all top-k lists.

• U = M j=1 L k (j)
is the union set of the M top-k lists. We will also denote K = #U, the number of elements in U.

• ∀i ∈ U : NZ(i, L k ) is the number of top-k lists in which object i appears.

Using these notations, we can define below the general linear combination which represents the baseline methods for rank aggregation issues in information retrieval [START_REF] Fox | Combination of multiple searches[END_REF], ∀i ∈ U:

Comb v,w (i) = NZ(i, L k ) v M j=1 w j S j (i) (1)
where v is an integer and w a (M × 1) vector of weights.

In this kind of approach, the most usual particular cases employed are the following ones [START_REF] Fox | Combination of multiple searches[END_REF], ∀i ∈ U:

CombSUM(i) = M j=1 S j (i) (2)
CombMNZ(i) = NZ(i, L k ) M j=1 S j (i) (3)
Other methods have been proposed for learning the weight vector w in an unsupervised manner. In [START_REF] Klementiev | An unsupervised learning algorithm for rank aggregation[END_REF] for example, an unsupervised learning algorithm is suggested. However, this approach is a linear combinations of scores. In our case, we rather use non linear aggregation operators.

Normalization step

The normalization step is inherent to any positional methods. Indeed, each expert may have its own particular score distribution which belongs to a certain range of values. As a result, before applying any aggregation function, we have to normalize each distribution if we want them to be mutually comparable. It exists several normalization methods [START_REF] Renda | Web metasearch : rank vs score based rank aggregation methods[END_REF]. However, in our particular case, the aggregation operators we are going to introduce have a fuzzy logic flavor. In other words, they aggregate truth values that belong to [0, 1]. Thus, we propose to normalize the experts' scores as follows.

Let us denote by V j (i), the original score value the expert j assigns to object i. Then, its associated normalized score denoted by S j (i) is given by, ∀j = 1, . . . , M ; ∀i ∈ L k (j):

S j (i) = V j (i) -min i ∈L k (j) {V j (i )} max i ∈L k (j) {V j (i )} -min i ∈L k (j) {V j (i )} (4)
With respect to expert j, the previous normalization formula is given for all objects belonging to the expert's top-k list, L k (j). We still need to assign normalized scores to objects that belong to U -L k (j). The only thing we can assume about these last objects is that they are not preferred to any of the objects belonging to L k (j). Consequently, ∀j = 1, . . . , M ; ∀i ∈ U -L k (j), we put: S j (i) = 0.

Some aggregation operators defined in information fusion

Many aggregation functions have been defined in the field of information fusion. We recall some of them namely triangular norms, triangular conorms and quasi-arithmetic means. These functions will be tested in our experiments in section 6.

Triangular norms and conorms

Triangular norms (t-norms in short) are binary operations T : [0, 1] 2 → [0, 1] which are associative, commutative, non decreasing in each argument and such that T (a, 1) = x, ∀a ∈ [0, 1]. They are special functions used in probabilistic metric spaces [START_REF] Schweizer | Probabilistic metric spaces[END_REF], and fuzzy logic [START_REF] Klement | Triangular norms[END_REF].

In fuzzy logic particularly, these operations extend the conjunction from the binary case to the multi-valued case. Let A and B be two events 1 and µ(A) = a and µ(B) = b their associated truth values in [0, 1]. Then, T (a, b) measures the truth value of the conjunction A ∩ B. As t-norms are associative and commutative, they can easily be extended for measuring the conjunction of more than two events. We have for example: T (a, b, c) = T (T (a, b), c) and so on.

When using t-norms as aggregation operators, we measure the conjunction of the events to be combined. In our case, we measure the truth value of "object i is relevant for all experts". However, the disjunction of these events is also of interest. Then, departing from a t-norm T , we can define its related triangular conorm T * (t-conorm in short) as follows, which allows to extend the disjunction to the multivalued case:

T * (a, b) = 1 -T (1 -a, 1 -b) (5)
Thus, by using t-conorms as aggregation operators, we measure the truth value of the event, "object i is relevant for at least one expert".

It exists non-parametric and parametric t-norms and tconorms. The four fundamental non-parametric ones are:

• the minimum t-norm and its related t-conorm:

T M (a, b) = min(a, b) (6) T * M (a, b) = max(a, b) (7)
• the product t-norm and its related t-conorm:

T P (a, b) = ab (8) T * P (a, b) = a + b -ab (9)
1 Typically, in our case, events are for example: "object i is relevant for expert j"

• the Lukasiewicz t-norm and t-conorm:

T W (a, b) = max(a + b -1, 0) (10) T * W (a, b) = min(a + b, 1) (11)
• the drastic product and its related t-conorm:

T D (a, b) = 0 if (a, b) ∈ [0, 1[ 2 min(a, b) otherwise (12) T * D (a, b) = 1 if (a, b) ∈]0, 1] 2 max(a, b) otherwise (13)
T M and T D are respectively, upper and lower bounds for t-norms. Thus, ∀T as a t-norm; ∀(a, b) ∈ [0, 1] 2 :

T D (a, b) ≤ T (a, b) ≤ T M (a, b) (14)
T M gives the highest value for the conjunction of two events: it assumes that one event is included in the other one and thus a positive dependence between them. T P gives the conjunction value of two events assuming that these last ones are independent. On the contrary, T W which is lower than T P , supposes that there is a rather negative dependence between the events. Finally, T D gives a zero value to the conjunction of two events unless one of the two has a truth value 1.

It also exists numerous parametric t-norms and tconorms. However, we will introduce only one pair of them: the Schweizer-Sklar family for which the non-parametric tnorms and conorms are particular cases.

The Schweizer-Sklar t-norm is given by, ∀λ ∈ [-∞, ∞]:

T λ SS (a, b) =    T M (a, b) λ = -∞ T P (a, b) λ = 0 T D (a, b) λ = ∞ (15)
and for λ ∈] -∞, 0[∪]0, ∞[, we have:

T λ SS (a, b) = max(a λ + b λ -1, 0) 1 λ
Its corresponding t-conorm is as follows:

T * λ SS (a, b) =    T * M (a, b) λ = -∞ T * P (a, b) λ = 0 T * D (a, b) λ = ∞ (16)
and for λ ∈] -∞, 0[∪]0, ∞[, we have:

T * λ SS (a, b) = 1 -max((1 -a) λ + (1 -b) λ -1, 0) 1 λ
As mentioned beforehand, t-norms or t-conorms can be used as aggregation operators. In that case they represent two extreme point of views which are respectively the conjunction and the disjunction over all events. On the contrary, mean operators are more compromise. According to [START_REF] Bloch | Information Combination Operators for Data Fusion: A Comparative Review with Classification (invited conference)[END_REF], we have the following classification:

T (a, b) ≤ min(a, b) ≤ M(a, b) ≤ max(a, b) ≤ T * (a, b)
where M is a mean operator.

As we will see in our experiments, due to their limit behaviors, t-norms and t-conorms don't fit well to meta-search problems. T-norms are too strict and they perform very badly. T-conorms perform better than t-norms but still, they are not able to reach the baseline results. Nevertheless, we mention, in section 6, the results obtained using different tconorms. As a result, in meta-search problems, we must use more compromise operators than t-norms or t-conorms. In that perspective, we introduce in the following paragraph, quasi-arithmetic means.

Quasi-arithmetic means

Quasi-arithmetic means, also called generalized fmeans, are operators that generalize the classical arithmetic mean by using a transformation function f . In our case, we will consider f : [0, 1] → [-∞, ∞]. f must be continuous, strictly monotone, and it must also respects the following conditions: {f (0), f (1)} = {-∞, ∞}. The quasiarithmetic mean associated to f is denoted M f . Given a sequence of M values {a 1 , . . . , a M } ∈ [0, 1] M , the quasiarithmetic mean of this sequence is defined by:

M f (a 1 , . . . , a M ) = f -1   1 M M j=1 f (a j )   (17)
We will consider more particularly, the case of power functions f (a) = a p with p ≥ 1 which are strictly monotonic functions. We remark that CombSUM is obviously equivalent to the arithmetic mean. To go further, we present in our experiments in section 6, the results obtained with p = 2 (quadratic mean). As we will see, this function outperforms the CombSUM results.

A new consensus aggregation operator

In addition to the previous aggregation functions, we introduce a new method which also presents interesting results on the LETOR datasets [START_REF] Liu | Letor: Benchmark dataset for research on learning to rank for information retrieval[END_REF], compared to baseline methods. Unlike the t-norms and t-conorms methods recalled beforehand, which are extreme point of views, the proposed approach is more consensus. Thus, it is comparable to quasi-arithmetic means. However, unlike this last method, our approach allows to take into account different types of dependencies between experts using different t-norms.

Definition and logical foundations

Let us denote by S j (i) the event: "object i is relevant for expert j". If we consider all M experts, we can define the following event: "object i is relevant for at least m experts among M ". Formally, this last event that we will denote E M m (i) is given by the following formula, ∀m = 1, . . . , M ; ∀i = 1, . . . , K:

E M m (i) = 1≤j1<...<jm≤M
(S j1 (i), . . . , S jm (i)) [START_REF] Liu | Letor: Benchmark dataset for research on learning to rank for information retrieval[END_REF] Given the truth value, S j (i) ∈ [0, 1], of event S j (i), we are interested in computing the truth value of event E M m (i) which will be denoted E M m (i). This is a combinatorial problem which generalizes Poincaré's formula2 also known as the "inclusion-exclusion principle". It has been shown in [START_REF] Ah-Pine | Sur des aspects algébriques et combinatoires de l'Analyse Relationnelle[END_REF] that E M m can be expressed as a linear combination of the following quantities, ∀i = 1, . . . , K:

• for l = 1:

S M l (i) = M j=1 S j (i) (19)
• for l = 2, . . . , M :

S M l (i) = 1≤j1<...<jl≤M T (S j1 (i), . . . , S jl (i)) ( 20
)
where T is a t-norm or a conjunction operation. This linear combination is related to Jordan's combinatorial formulas [START_REF] Jordan | Problèmes de la probabilité des épreuves répétées dans le cas général[END_REF], [START_REF] Comtet | Analyse Combinatoire, tome 1 et tome 2[END_REF], and we have, ∀m = 1, . . . , M ; ∀i = 1, . . . , K:

E M m (i) = M l=m (-1) l-m l -1 m -1 S M l (i) (21)
where n p = n! p!(n-p)! , are binomial coefficients. Now that we have introduced the consensus measures E M m ; m = 1, . . . , M , we make a simple assumption on which our aggregation function is based: the greater the number of experts who find object i relevant, the higher the aggregated score corresponding to object i must be3 [START_REF] Lee | Analyses of multiple evidence combination[END_REF].

In a literal formulation, our aggregation function can be defined as follows : we weight by m the measure that object i is relevant for at least m experts then we sum over m from 1 to M . As the proposed method gives increasing weights Figure 1. Illustration of the combinatorial "trick" with 3 experts when m, the number of considered experts, grows, it is a method that respect the property we are looking for.

We denote our consensus aggregation function A. It is formally defined by the following equation, ∀i = 1, . . . , K:

A(i) = M m=1 mE M m (i) (22)
We may also consider a normalized version by dividing ( 22) by M (M +1) 2 . In its original formulation given by equations ( 21) and ( 20), the computation cost of A(i) is expensive. Indeed, in order to compute S M l (i) in [START_REF] Michaud | Modèles d'optimisation en analyse des données relationnelles[END_REF], we need to enumerate M l combinations which grows exponentially. But, as we will show in the following paragraph, using combinatorial properties, we can reduce the computational cost of A(i) to O(M 2 ).

The combinatorial "trick"

From equation [START_REF] Renda | Web metasearch : rank vs score based rank aggregation methods[END_REF] which has an exponential computational cost, we can prove the following statement which allows to reduce significantly the computational cost of the proposed consensus aggregation operator, ∀i = 1, . . . , K:

A(i) = M j=1 S j (i) + 1≤j<j ≤M T (S j (i), S j (i)) (23)
Given equation ( 23), we can see that our proposal goes beyond a simple sum 4 as the proposed aggregation function allows to take into account pairwise conjunctions between experts. Particularly, we can specify the type of relationship between each pair of experts by using different t-norms such as introduced in paragraph 4.1.

We give in figure 1, an illustration of the property for M = 3. We give the proof of the combinatorial "trick" which allows to obtain the reduced form [START_REF] Riker | Liberalism against populism[END_REF] in appendix. 4 As the first part is similar to CombSUM.

Experiments and results

In this section, using numerical examples, we show that the proposed aggregation operators can perform better than baseline approaches.

We tested the different methods introduced previously, on the three different datasets of the LETOR package [START_REF] Liu | Letor: Benchmark dataset for research on learning to rank for information retrieval[END_REF]:

• OHSUMED dataset (subset of MEDLINE, a database of medical publications): 106 queries, 25 different ranking features (the experts)

• TREC 2003 web track (topic distillation task): 50 queries, 44 different ranking features (the experts)

• TREC 2004 web track (topic distillation task): 75 queries, 44 different ranking features (the experts)

For each datasets, we have different queries (topics) and for each ranking features, we are given a distribution of scores among a set of objects (medical publications or html files). The ranking features are either low-level or high-level content features, between each judged querydocument pairs. The reader can consult [START_REF] Liu | Letor: Benchmark dataset for research on learning to rank for information retrieval[END_REF], for a more detailed description of the characteristics of these datasets and for the definition of the features that were extracted.

The LETOR dataset was initially constituted for benchmarking "learning to rank" methods. In that context the goal is to learn, from a training set, how to combine the different experts. In our case, we are in an unsupervised context and we only use the relevance file for measuring a posteriori the performances of the proposed methods.

First, we normalized the data using the score normalization 5 given by ( 4) with k = 1000. Then, we computed the following aggregation functions: CombSUM (equivalent to M f with f (a) = a), CombMNZ, the quadratic mean (M f with f (a) = a 2 ) and the new aggregation method A using either non-parametric t-norms or the parametric t-norm T λ SS with λ = 2.

For measuring and comparing the performances of the different aggregation methods, we used the trec eval tool 6 and we retained the mean average precision (MAP) and the precision at 5 (P@5) measures. The results are given in tables 1, 2 and 3. In italic are the baseline results given by CombSUM. We put in bold the best result with respect to the MAP, among the aggregation operators we tested.

These results show that quadratic means and our aggregation function outperform the baseline results whereas the t-conorms perform very poorly except for the OHSUMED dataset. It is not clear if our approach is better than quasiarithmetic means as there is little differences between both of them in terms of MAP or P@5. We could have tested M f with f (a) = a p and p ≥ 3. This may give better results than the one obtained using A. However, we could also tune the parameter λ when applying A with a parametric t-norm.

Finally, despite quite similar results, both methods are different. We argue in favor of our approach as it has deep logical foundations, and as it also allows to model the relationships between experts using different t-norms unlike quasi-arithmetic means. In our experiments, we assumed that all pairs of experts had the same kind of relationships. In a more general perspective, a better expertise of the dependencies between the features, can be taken into account by choosing for each pair of features a different conjunction operation.

Conclusion

In this paper, we address data fusion problems. We are particularly concerned with unsupervised rank aggregation issues in information retrieval field. The general aim of this work is to investigate the use of some aggregation operators defined in information fusion field in the context mentioned beforehand. We have recalled and tested classic aggregation operators such as t-conorms and quasi-arithmetic means. We have moreover introduced a new aggregation method A, its logical foundations and its combinatorial properties.

Our experiments on the LETOR dataset show that quasiarithmetic means and A operator can improve the baseline results. It also allows us to conclude that t-norms and tconorms are not good aggregation operators for that kind of issues and datasets as they are not enough compromise.

The results we obtain in an unsupervised manner are interesting compared to the ones obtained in a supervised manner 7 . Consequently, we intend to embed the methods described in this paper and particularly, the new aggregation function, in a supervised context. In that perspective, the concept of expert's reliability seems interesting to develop.

Acknowledgments

The author would like to thank Jean-Michel Renders for helpful comments.

A. Appendix: proof of the combinatorial "trick"

Proof. In order to prove the property given in equation ( 23), we will use the two following combinatorial identities 8 :

n p=0 (-1) p n p = 1 {n=0} (24) n p=0
(-1) p+1 n p p = 1 {n=1} (25) 7 For example, the baseline results in a supervised context for the OHSUMED dataset reach a MAP of approximately 44.00 % [START_REF] Liu | Letor: Benchmark dataset for research on learning to rank for information retrieval[END_REF]. We have seen previously that the best result we obtained in an unsupervised manner using A is 40.74 %. 8 For identities and properties referring to binomial coefficients and Pascal's triangle, a good reference is the following website [START_REF] Pascal | Pascal's triangle from top to bottom[END_REF].

Table 1 . Results for the OHSUMED dataset

 1 SS , λ = 2 17.37 % 17.60 %

	Method	MAP	P@5
	CombSUM	39.52 % 47.36 %
	CombMNZ	38.68 % 46.98 %
	Quadratic mean	40.39 % 49.25 %
	T * M T * P T * W	39.71 % 49.25 % 37.32 % 40.94 % 29.97 % 26.98 %
	A with T M	38.49 % 46.60 %
	A with T P	39.44 % 47.17 %
	A with T W	40.23 % 49.81 %
	A with T SS , λ = 2 40.74 % 50.19 %
	Method	MAP	P@5
	CombSUM	16.83 % 16.80 %
	CombMNZ	15.42 % 14.40 %
	Quadratic mean	16.57 % 16.80 %
	T * M T * P T * W	07.98 % 07.20 % 04.40 % 03.20 % 01.27 % 01.20 %
	A with T M	15.86 % 14.00 %
	A with T P	16.81 % 16.40 %
	A with T W	17.04 % 17.60 %
	A with T

Table 2 . Results for the TREC 2003 dataset

 2 SS , λ = 2 29.56 % 21.87 %

	Method	MAP	P@5
	CombSUM	26.81 % 22.13 %
	CombMNZ	23.09 % 20.53 %
	Quadratic mean	29.41 % 21.87 %
	T * M T * P T * W	07.93 % 04.80 % 04.59 % 02.40 % 07.60 % 00.00 %
	A with T M	22.63 % 20.80 %
	A with T P	26.78 % 22.13 %
	A with T W	29.00 % 21.60 %
	A with T

Table 3 . Results for the TREC 2004 dataset

 3

Poincaré's formula corresponds to the case m = 1.

Notice that baseline methods given in (1) pursue the same goal by weighting by NZ(i, L k ) v the experts' score sum. However, our proposal is a different approach which is rather based upon a logical definition.

We found that it may happen that for some features, a unique value is assigned to all objects. In that case, we replaced this value by 0.

cf. http://trec.nist.gov/

where 1 {A} is the indicator function which equals 1 if proposition A is true; 0 otherwise. We first have:

Then we denote m = m -1; l = l -1 and M = M -1.

Using these variables we obtain:

Next, if we enumerate a bit this last expression with respect to l , we can see that using the combinatorial identities given in ( 24) and ( 25): we obtain S M 1 (i) for l = 0; S M 2 (i) for l = 1 and a null quantity for l > 1. This shows finally that A(i) = S M 1 (i) + S M 2 (i) which is the same as [START_REF] Riker | Liberalism against populism[END_REF].