Dinu Coltuc
email: dinu.coltuc@lis.inpg.fr

Jean-Marc Chassery
email: jean-marc.chassery@lis.inpg.fr

Mapping Based Reversible Watermarking

Keywords: embedding bit-rate, integer mapping, reversible watermarking

The set of pairs of pixels is partitioned into disjoint groups of equal number of pairs. Furthermore, a subset of pairs of pixels is selected and each pair is uniquely associated with a group of the partition. If the size of the groups is m, log2m bits of data can be embedded into an image pair by replacing it by the pairs of a group. As long as at detection one can find if a pair was replaced or not, the transform is reversible. Hence a reversible watermarking scheme is obtained by embedding together with the watermark the information needed to locate the transformed pairs. The paper discusses how to select the subset of pixel pairs and the partition in order to obtain high capacity watermarking schemes. It is also shown that a recently proposed reversible scheme is based on this principle. Due to its flexibility, the general scheme is expected to introduce less distortion. The experimental results obtained so far are promising.

INTRODUCTION

Reversible watermarking (also known as lossless, distortion-free, invertible) removes completely the watermark and exactly recovers the original signal/image. This subject is of considerable interest in some special domains where no loss of information is accepted. There are also reversible watermarking schemes that do not need explicit data compression algorithms. We mention the circular histogram interpretation [VLE 03] and the simple reversible watermarking schemes [COL 05] [COL 06b].The drawback of histogram based scheme, as well as of some other schemes where data is embedded on some statistics taken over blocks of pixels, is their low embedding capacity. By the contrary, the simple schemes, [COL 05] [COL 06b], provide high-capacity embedding bite-rates. They outperform the generalized LSB embedding scheme and they provide almost similar bit-rates as the difference expansion schemes. The simple schemes are of very low computational complexity. A weakness of these simple schemes is the distortion introduced by the watermarking, especially at high bit-rates. While at bit-rates lower than 0.5 bpp, the watermarking is imperceptible, as the bit-rate increases, the distortions increases as well and the marked images look noisy. It should be noticed that, since the watermarking is reversible, at detection the authorized party can recover the original image without any distortion.

The simple schemes, [COL 05] [COL 6b], are based on some integer invertible transforms defined on groups of n pixels, where n>1. Groups obeying some simple constraints are transformed and furthermore, data is embedded into the transformed groups. The transforms induce some properties allowing reversible data embedding. For the original simple scheme [COL 05] [COL 6a], the transform is robust in the sense that the inverse transform gives exact results even if the LSBs of the transformed groups are lost. Thus, space is created into the LSB plane for data insertion. In order to retrieve the pairs that have been transformed, a location map should be stored together with the watermark. The location map needs one bit for each group of n pixels. Furthermore each transformed group provides n-1 bits for data embedding. The scheme works if there are more than 1/n transformed groups from the total number of groups. For groups of two pixels, the scheme provides

SETIT2007

-2 -at maximum 0.5 bpp per iteration. For n>2, the scheme may provide in a single iteration more than 0.5 bpp, but the bit-rate per iteration is bounded by 1 bpp. In order to increase the bit-rate, multiple iterations are performed. Usually, for natural images, the bit-rate provided for data hiding is of the order of 1.5 bpp.

The high-capacity simple scheme, [COL 6b], works on pairs of pixels, but uses a slightly different transform. Pairs obeying some simple constraints are transformed in order to satisfy a congruence equation. By adding some correction data, the not transformed pixel pairs are enforced to obey the same equation, too. By simple additions, the watermark together with the correction data is embedded into the transformed pixels. After watermark insertion, only the not transformed pixel pairs satisfy the congruence equation. Hence, at detection, the transformed pairs can be localized. Finally, the watermark and correction data can be extracted and the exact recovery of the original image follows by inverse transform. The high capacity scheme can provide, in a single iteration, more than 1 bpp. This paper investigates a general mapping based reversible watermarking. The proposed watermarking scheme can be seen as an extension of the simple reversible schemes discussed above [COL 05] [COL 06b]. The new watermarking scheme is intended to preserve the high capacity and the low cost of the simple schemes and besides, to introduce less distortion. The principle of the watermarking is discussed in Section 1. The watermarking scheme is presented in Section 2. An example of reversible watermarking is analyzed in Section 3. Conclusions are drawn in Section 4.

Watermarking Principle

Let us first analyze the high capacity reversible scheme [COL 06b] and then, introduce the principle of the proposed general mapping watermarking. As said above, the scheme transforms pairs of pixels, (x,y), into pairs of pixels, (X,Y). The transform T is given by the equations:

X=(p+1)x-py; Y=(p+1)y-px

(1) where p is an integer. The transform used in [COL 05] is recovered from equations (1) by taking the integer p equal to 1, transform which is further extended in [COL 06a] for groups of n pixels.

Let [0,L-1] be image graylevel range, i.e., x, y, X, Y are integers in [0,L-1].Conditions to avoid pixel overflow or underflow are imposed:

0≤X≤L-1; 0≤Y≤L-1 (2)
From (2) it appears that the transform is not defined on the entire integer grid [0,L-1]x[0,L-1], but only on a subset. In the plane xy, equations (2) define a rhombic subdomain located along the main diagonal of [0,L-1]x[0,L-1]. Let D be the set of pixel pairs corresponding to the rhombic subdomain. The subdomain is transformed by T in parallel lines, parallel with the diagonal of [0,L-1]x[0,L-1]. The distance on the integer grid between the lines on horizontal (equivalently, vertical) direction is 2p+1.

The scheme provides an embedding capacity of log 2 (2p+1) bits per transformed pair. This is done by adding an integer ranging in [0,2p] to the first pixel of any transformed pair. Hence the data embedding is performed by transforming a pair of pixels belonging to D and then by selecting a pair from [0,L-1]x[0,L-1] located on vertical direction in the neighborhood of the transformed one.

In fact, the reversible watermarking scheme partitions the integer grid [0,L-1]x[0,L-1] in groups of 2p+1 integers located on vertical direction. This corresponds to a partition of the entire pairs set in groups of 2p+1 pairs. In each group, there is only a single pair (X,Y) such that (X,Y)=T(x,y), where (x,y) belongs to D. At detection, once a pair is identified as a transformed one, the group of 2p+1 pixel pairs of the partition is identified, too. The embedding data is extracted and then, by inverting equations (1), the original pair of pixels is recovered. Some additional data, like a location map, should be embedded together with the watermark in order to provide, at detection, the information needed to identify the transformed pairs.

The scheme provides high capacity data embedding since there is a great number of image pixel pairs belonging to D. This is due to the fact that in homogenous areas pixels have graylevels close to each others and the pairing is performed by taking adjacent pixels. Therefore a large number of pairs are located along the diagonal of [0,L-1]x[0,L-1].

To conclude, a reversible watermarking scheme is obtained by defining a partition of the set of graylevel pairs in groups of m pairs and by defining a certain one to one mapping, too. Each pair of a group of m can encode an integer in the range [0,m-1]. Furthermore, pixel pairs are transformed according to the mapping and data is embedded by taking the appropriate pair within the group of m. Such a scheme provides log 2 m bits per transformed pair.

With respect to the hiding bit-rate, the reversible watermarking scheme is of interest if the mapping is defined on a subset which is very well represented among the pairs obtained by grouping image adjacent pixels. This is exactly what the scheme of [COL 06b] is doing. As discussed above, the equations (1) define the mapping between the pixel pairs set defined by equations (2) and some pairs of [0,L-1]x[0,L-1] set. The equations (1,2) are simple and give an elegant setting of the reversible watermarking.

The general framework proposed in this paper allows more flexibility, since no a priori constraints exists neither for the mapping nor for the partition. By a better selection of the partition, we expect to obtain less distortion at the same bit-rate than for the scheme of [COL 06b].

SETIT2007

-3 -

Reversible Watermarking Scheme

The mapping

The essential element of the reversible watermarking scheme is the mapping. The mapping is defined on a certain subset D of entire set of pairs, the Cartesian product [0,L-1]x[0,L-1]. Let N be the number of pixel pairs of D.

Let m be the number of pairs of the groups. Obviously, the set of pixel pairs [0,L-1]x[0,L-1] has L 2 distinct elements. In order to have a one to one mapping, m should be less than L 2 /N. It should be noted that larger m, greater the bit-rate provided by the scheme. Meantime, a large m will increase the distortions introduced by the watermarking. Examples for different values of m will be given in the next section.

Once m selected, we define the partition of the set of pairs in groups of m. For the case m=r 2 (or similarly, m=rq), the set [0,L-1]x[0,L-1] can be simply partitioned in squares of size rxr or, generally, in rectangles of size rxq). For the case arbitrary m, we consider the following procedure. Since L is generally a power of two (L=256 for 8 bit graylevel images), the set [0,L-1]x[0,L-1] can be traversed by a Peano curve. We mention that Peano curve achieves a good compromise between one-dimensional and twodimensional neighborhoods -in the sense that, broadly speaking, points that are nearby in the twodimensional domain are nearby along the Peano curve and conversely. Peano curve introduces an ordering on the two-dimensional set of pixel pairs. Then, starting from an endpoint of the curve and following the curve, the groups of m pairs are constructed. The procedure ensures that the pairs grouped together have quite similar graylevel values for each component.

For each group, a representative pair is selected. First the pairs of the group are averaged and then, the representative is selected as the pair having the minimum Euclidean distance to the average. The mapping between D and the N representative pairs of [0,L-1]x[0,L-1] is further determined by minimizing the mean squared error between the pairs of D and the corresponding representatives. Finally, the encoding of embedded data on each group is defined. We consider that selecting the representative pixel pair means the encoding of '0'. The other (m-1) pairs of each group encode the integers from '1' to 'm-1'. Thus, by selecting a certain pair within the group of a transformed pair, a codeword in [0,m-1] is embedded. Now, the mapping is completely defined.

Marking

The marking proceeds as follows:

1. Partition entire image in pairs of pixels; 2. Transform the pairs belonging to D according to the mapping and create a location map accordingly;

3. Embed the watermark by replacing the transformed pair with the pair of the group corresponding to the integer codeword to be inserted.

Image partition in pairs of pixels can be made along rows, columns or any space filling curve. The only constraint imposed for the pairing is to have adjacent pixels.

The watermark consists of the location map, the payload and some data to validate the integrity of the watermark. For watermarking integrity validation, a cyclic redundancy check (CRC) is sufficient.

An improvement in data hiding capacity can be achieved by storing only a partial location map. If after the mapping and the data encoding steps the resulted pair still belongs to D, then such a pair can be non ambiguously identified at detection. Therefore it is not necessary to use a bit in the location map to record its status. Let us suppose that a scanning order is defined. Then, the data embedding step will not start with the first pair in the scanning order which belongs to D, but with the first pair which can be non ambiguously identified at detection. The embedding will continue with the second such pair and so on. After all such pairs are processed, the embedding is performed, in the scanning order, for the skipped pairs.

Detection and original recovery

The detection procedure immediately follows. The pairs are taken in the scanning order and the pairs non ambiguously detectable are first processed. For each pair, the group to which the pair belongs is first found. Then the embedded data is decoded. At marking, data embedding starts with the location map. Therefore, at detection, the bits of the location map are first recovered. After the end of the set of non ambiguously detectable pairs, the decoding goes on in the scanning order according to the location map. The identified pairs are decoded and the remaining bits of the location map and the payload are extracted.

After watermark extraction, the original image recovery follows. For each transformed pair, the representative pair of the group is identified and then inverted to recover the original pixel values.

An example

A domain D constituted of 4093 pairs of pixels has been considered. As discussed in Section 1, pairs close to the diagonal of [0,L-1]x[0,L-1] have been selected. In the xy plane, the shape of the domain is an ellipse, as shown in Fig. 1. For mappings of D on [0,L-1]x[0,L-1] are derived for m=4, 8, 12 and16, respectively.

SETIT2007

-4 - The watermarked version for m=4 (Fig. 3) provides a data embedding bit-rate of 0.65 bpp. The reported bit-rate takes into account only the effective data space available for storing the payload, i.e., after the embedding of the location map. The PSNR of the marked image is of 32.82 dB.

The watermarking scheme obtained by considering the mapping for m=8 provides, for the same test

SETIT2007

-5 -image, a bit-rate of 0.99 bpp at a PSNR of 25.93 dB. The marked image is shown in Fig. 4. Furthermore, for m=12, the bit-rate is 1.21 bpp at a PSNR of 22.45 dB (Fig. 5). Finally, a bit-rate of 1.37 bpp at a PSNR of 19.62 dB is obtained in the case m=16.

With respect to the embedding bit-rate, the results are similar to the one reported in [COL 06b]. Similar to the high capacity watermarking of [COL 06b], the scheme can provide in a single iteration more than 1 bpp (as in the case m=3 and m=4). Furthermore, by chaining multiple watermarking steps, an increase of the embedding bit-rate can be obtained. The mathematical complexity of the watermarking is low: no additional data compression is needed.

The watermarked image shown in Fig. 3 provides 0.64 bpp at a PSNR of 32.82 dB. This appears to be a significant improvement with respect to [COL 06], where a bit-rate of 0.49 bpp was obtained for the same test image at a PSNR of 29 dB. As the bit-rate increases, the distortion increases, too.

Conclusions

A general framework for reversible watermarking was proposed. The set of pairs of pixels is partitioned into disjoint groups of m pairs. Meantime, a subset of pairs of pixels is selected and each pair is uniquely associated with a group of the partition. Then log 2 m bits of data can be embedded into an image pair by replacing it with the pairs of its corresponding group. The paper discusses how to define such a partition and how to select the subset of pixel pairs in order to derive high capacity reversible schemes. The derived schemes are of low mathematical complexity. No additional data compression is needed. The high capacity reversible watermarking [COL 06b] is a particular case of mapping based reversible watermarking schemes.

By an appropriate choice of the partition, the general approach introduces less distortion at the same embedding bit-rate. Such an example is provided. The results obtained so far are promising. More experimental results will be provided in the full paper version.

Further mappings and partition strategies are under investigation. The objective is to improve the quality of the marked images for high embedding bit-rates.

  So far, several reversible watermarking approaches have been proposed [FRI 02] [TIA 03] [ALA 04] [CEL 05] [VLE 03] [COL 05] [COL 06b]. Most of them must apply lossless data compression to gain space for data embedding [FRI 02] [TIA 03] [ALA 04] [CEL 05]. Among these, the highest embedding bitrates are provided by the generalized LSB embedding [CEL 05] and notably, by the difference expansion schemes [TIA 03] [ALA 04] [KAM 05].

Fig. 1 .

 1 Fig.1. Representation of the mapping domain D.

Fig. 2 .

 2 Fig. 2. Original test image.

Fig. 3 .

 3 Fig.3. Marked image for m=4: 0.64 bpp at 32.82 dB.

Fig. 4 .

 4 Fig. 4. Marked image for m=8: 0.99 bpp at 25.93 dB.

Fig. 5 .

 5 Fig. 5. Marked image for m=12: 1.21 bpp at 22.45dB.

ACKNOWLEDGMENT

This work is supported by the project ARA-TSAR from ANR, France.


Gr Égoire Pichon

Eric Darve

Mathieu Faverge

Pierre Ramet

Jean Roman

Sparse Supernodal Solver exploiting Low-Rankness Property September 6th, 2017 -Sparse Days

Introduction

Current sparse direct solver for 3D problems

• Θ(n 2 ) time complexity Objective: build an algebraic low-rank solver following the supernodal approach of PASTIX, with block-data structures

Symbolic Factorization

General approach

1. Build a partition with the nested dissection process

Compress information on data blocks

3. Compute the block elimination tree using the block quotient graph Adjacency graph (G). Elimination tree (T).

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Factorized matrix (L).

Operations

• Diagonal blocks are dense

• TRSM are performed on low-rank off-diagonal blocks

• GEMM are performed between low-rank off-diagonal blocks. It creates contributions to dense or low-rank blocks: this is the extend-add problem

Compression techniques

• SVD, RRQR for now Algorithm • Atmosmodj: atmospheric model (1 270 432 dofs)

A = uC v t C +uABv t AB = [uC , uAB] × [vC , vAB] t • QR: [uC , uAB] = Q1R1 Θ(m(rC + rAB) 2 ) • QR: [vC , vAB] = Q2R2 Θ(n(rC + rAB) 2 ) • SVD: R1R t 2 = uσv T Θ((rC + rAB) 3 ) A = Q1uσ × Q2v
• Geo1438: geomechanical model of earth (1 437 960 dofs)

• Hook: model of a steel hook (1 498 023 dofs)

• Serena: gas reservoir simulation (1 391 349 dofs)

Parameters

Entry parameters

• Tolerance τ : absolute parameter (normalized for each block)

• Compression method: SVD or RRQR

• Compression strategy: Minimal Memory or Just-In-Time

• Blocking sizes: between 128 and 256 in following experiments

Strategy Minimal Memory

• Blocks are compressed at the beginning

• Each contribution implies a recompression
Strategy Just-In-Time

• Blocks are compressed just before a supernode is eliminated Scaling on Laplacians: Memory Consumption RRQR/Minimal Memory 1 0 0 3 1 1 0 3 1 2 0 3 1 3 0 3 1 4 0 3 1 5 0 3 1 6 0 3 1 7 0 3 1 8 0 3 1 9 0 3 2 0 0 3 2 1 0 3 2 2 0 3 2 3 0 3 Size • Double interaction: between S and SA and between S and SB in the original graph

• Three "large" interaction blocks during the factorization

• Θ(n 4 3

 4 ) memory complexity • BLAS 3 operations Block Low-Rank solver • Large blocks are compressed into a low-rank form • Operations keep untouched the global behaviour of PASTIX • Minimal Memory strategy allows to save memory • Just-In-Time strategy allows to reduce time-to-solution

0Machine: 2

 2 Optimizations using RRQR to reduce complexity to Θ(n(rC + rAB)r * C ) INTEL Xeon E5 -2680v3 at 2.50 GHz• 128 GB• 24 threads 3D Matrices from The SuiteSparse Matrix Collection• Audi: structural problem (943 695 dofs)

G•

  Factors size, τ =10 -4 Factors size, τ =10 -8 Factors size, τ =10 -12 Single interaction between S and SA ∪ SB in the original graph• Two large interaction blocks PA 1 ∪ PB 1 and PA 2 ∪ PB 2

Sparse Supernodal Solver exploiting Low-Rankness Property 3/23 Numerical Factorization

	1 1. Factorize the diagonal block (POTRF/GETRF) 2 3 2. Solve off-diagonal blocks in the current column (TRSM) 4 5 3. Update the trailing matrix with the column's contribution (GEMM) 6 7 Parallelism G. Pichon -Algorithm to eliminate the column block k • Right-Looking

• Left-Looking G.

Pichon -Sparse Supernodal Solver exploiting Low-Rankness Property 4/23 Block-Low-Rank Compression -Symbolic Factorization

	Large off-diagonal are low-rank, in the form uv t

G.

Pichon -Sparse Supernodal Solver exploiting Low-Rankness Property 5/23 Some Related Works

	Block Low-Rank solvers
	• BLR-MUMPS introduced an approach focused on reducing the time to
	solution which is close to our Just-In-Time strategy
	• LSTC developed compression/recompression techniques in a dense
	context
	Other approaches for sparse
	• Strumpack HSS by Ghysels et al. utilizes randomized sampling to
	perform an efficient extend-add
	• HODLR by Darve et al. uses pre-selection of rows and columns (BDLR)

• H-LU by Hackbusch et al. does not fully exploit the symbolic factorization G. Pichon -Sparse Supernodal Solver exploiting Low-Rankness Property 6/23 Block-Low-Rank Algorithm Approach • Large supernodes are partitioned into a set of smaller supernodes • Large off-diagonal blocks are represented as low-rank blocks

Pichon -Sparse Supernodal Solver exploiting Low-Rankness Property 9/23 Comparison of both strategies

  Factorize the dense diagonal block Compress off-diagonal blocks belonging to the supernode 1.2 Apply a TRSM on LR blocks (cheaper) 1.3 LR update on dense matrices (LR2GE extend-add)2. Solve triangular systems with low-rank blocks

	1. Eliminate each column block 1. Eliminate each column block 1. Eliminate each column block 1. Eliminate each column block 1. Compress large off-diagonal blocks in A (exploiting sparsity)
	1.1 Factorize the dense diagonal block Compress off-diagonal blocks belonging to the supernode 1.2 Apply a TRSM on LR blocks (cheaper) 1.3 LR update on dense matrices (LR2GE extend-add) 1.1 Factorize the dense diagonal block Compress off-diagonal blocks belonging to the supernode 1.2 Apply a TRSM on LR blocks (cheaper) 1.3 LR update on dense matrices (LR2GE extend-add) 1.1 Factorize the dense diagonal block Compress off-diagonal blocks belonging to the supernode 1.2 Apply a TRSM on LR blocks (cheaper) 1.3 LR update on dense matrices (LR2GE extend-add) 1.1 Factorize the dense diagonal block 1.2 Apply a TRSM on LR blocks (cheaper) 2.3 LR update on LR matrices (LR2LR extend-add) 1.3 LR update on dense matrices (LR2GE extend-add) 2.2 Apply a TRSM on LR blocks (cheaper) 2.1 Factorize the dense diagonal block Compress off-diagonal blocks belonging to the supernode 2. Eliminate each column block Memory consumption	vB	u t B
	2. Solve triangular systems with low-rank blocks 2. Solve triangular systems with low-rank blocks 2. Solve triangular systems with low-rank blocks 2. Solve triangular systems with low-rank blocks 3. Solve triangular systems with LR blocks C • uABv t AB = (uA(v t A vB))u t uABv t AB = uA((v t A vB)u t B ) uA B or A v t	uC	v t C
	• Eventually, recompression of
	Compression GETRF (Facto) TRSM (Solve) LR2LR (Update) LR2GE (Update) Compression GETRF (Facto) TRSM (Solve) LR2LR (Update) LR2GE (Update) Compression GETRF (Facto) TRSM (Solve) LR2LR (Update) LR2GE (Update) Compression GETRF (Facto) TRSM (Solve) LR2LR (Update) LR2GE (Update) LR2GE (Update) LR2GE (Update) LR2LR (Update) LR2LR (Update) TRSM (Solve) TRSM (Solve) GETRF (Facto) GETRF (Facto) Compression Compression (v t A vB)

• Possible extension to any algebraic method: ACA, randomized techniques...

1. Eliminate each column block

1.1 G.

• Minimal Memory strategy really saves memory • Just-In-Time strategy reduces the size of L' factors, but supernodes are allocated dense at the beginning: no gain in pure right-looking Low-Rank extend-add • Minimal Memory strategy requires expensive extend-add algorithms to update (recompress) low-rank structures with the LR2LR kernel • Just-In-Time strategy continues to apply dense update at a smaller cost through the LR2GE kernel G. Pichon -Sparse Supernodal Solver exploiting Low-Rankness Property 10/23 Focus on the LR2LR kernel • Update of C with contribution from blocs A and B • The low-rank matrix uABv t AB is added to uC v t G. Pichon -Sparse Supernodal Solver exploiting Low-Rankness Property 11/

23 LR2LR kernel using SVD

	A low-rank structure uC v t C receives a low-rank contribution uABv t AB .

Rankness Property 14/23 Costs distribution on the Atmosmodj matrix with

  τ = 10 -8

		Dense Dense	Just-In-Time RRQR SVD Just-In-Time RRQR SVD	Minimal Memory RRQR SVD Minimal Memory RRQR SVD
	Factorization time (s) Factorization time (s)
	Compression Compression	--	49.53 49.53	418.5 418.5	15.20 15.20	180.9 180.9
	Block factorization (GETRF) 0.9635 Block factorization (GETRF) 0.9635	1.000 1.000	1.003 1.003	1.074 1.074	1.104 1.104
	Panel solve (TRSM) Panel solve (TRSM)	15.80 15.80	6.970 6.970	6.526 6.526	11.16 11.16	6.946 6.946
	Update Update
	LR product LR product	--	64.10 64.10	91.15 91.15	193.1 193.1	94.36 94.36
	LR addition LR addition	--	--	--	774.6 774.6	6523 6523
	Dense udpate (GEMM) Dense udpate (GEMM)	418.7 418.7	47.94 47.94	47.03 47.03	--	--
	Total Total	436 436	169 169	564 564	995 995	6806 6806
	Solve time (s) Solve time (s)	2.43 2.43	1.54 1.54	1.8 1.8	2.22 2.22	1.29 1.29
	Factors final size (GB) Factors final size (GB)	15.9 15.9	7.4 7.4	6.86 6.86	11.4 11.4	6.76 6.76
	Memory peak (GB) Memory peak (GB)	15.9 15.9	15.9 15.9	15.9 15.9	11.4 11.4	6.76 6.76

• Those blocks are never uncompressed G. Pichon -Sparse Supernodal Solver exploiting Low-G. Pichon -

Sparse Supernodal Solver exploiting Low-Rankness Property 15/23 Costs distribution on the Atmosmodj matrix with

  τ = 10 -8

		Dense Dense	Just-In-Time RRQR SVD Just-In-Time RRQR SVD	Minimal Memory RRQR SVD Minimal Memory RRQR SVD
	Factorization time (s) Factorization time (s)
	Compression Compression	--	49.53 49.53	418.5 418.5	15.20 15.20	180.9 180.9
	Block factorization (GETRF) 0.9635 Block factorization (GETRF) 0.9635	1.000 1.000	1.003 1.003	1.074 1.074	1.104 1.104
	Panel solve (TRSM) Panel solve (TRSM)	15.80 15.80	6.970 6.970	6.526 6.526	11.16 11.16	6.946 6.946
	Update Update
	LR product LR product	--	64.10 64.10	91.15 91.15	193.1 193.1	94.36 94.36
	LR addition LR addition	--	--	--	774.6 774.6	6523 6523
	Dense udpate (GEMM) Dense udpate (GEMM)	418.7 418.7	47.94 47.94	47.03 47.03	--	--
	Total Total	436 436	169 169	564 564	995 995	6806 6806
	Solve time (s) Solve time (s)	2.43 2.43	1.54 1.54	1.8 1.8	2.22 2.22	1.29 1.29
	Factors final size (GB) Factors final size (GB)	15.9 15.9	7.4 7.4	6.86 6.86	11.4 11.4	6.76 6.76
	Memory peak (GB) Memory peak (GB)	15.9 15.9	15.9 15.9	15.9 15.9	11.4 11.4	6.76 6.76

G. Pichon -Sparse Supernodal Solver exploiting Low-Rankness Property 7/23

G. Pichon -Sparse Supernodal Solver exploiting Low-Rankness Property 8/23

G. Pichon -Sparse Supernodal Solver exploiting Low-Rankness Property

G. Pichon -Sparse Supernodal Solver exploiting Low-Rankness Property 9/23

G. Pichon -Sparse Supernodal Solver exploiting Low-Rankness Property 15/23

G. Pichon -Sparse Supernodal Solver exploiting Low-Rankness Property 20/23

Costs distribution on the

• The version presented follows the parallelism of PASTIX

• On-going work to implement efficiently this approach over the PARSEC runtime system

Ordering strategies

• Study of a nested dissection designed to increase compressibility


Andon Tchechmedjiev

Amine Abdaoui

Vincent Emonet

Clement Jonquet

ICD-10 coding of death certificates with the NCBO and SIFR Annotators at CLEF eHealth 2017

Keywords: Semantic annotation, SIFR Annotator, NCBO Annotator, ICD-10 coding, Biomedical ontologies

The SIFR BioPortal is an open platform to host French biomedical ontologies and terminologies based on the technology developed by the US National Center for Biomedical Ontology (NCBO). The portal facilitates the use and fostering of terminologies and ontologies by offering a set of services including semantic annotation. The SIFR Annotator (http://bioportal.lirmm.fr/annotator) is a publicly accessible, easily usable ontology-based annotation tool to process French text data and facilitate semantic indexing. The web service relies on the ontology content (preferred labels and synonyms) as well as on the semantic of the ontologies (is-a hierarchies) and their mappings. The SIFR BioPortal also offers the possibility of querying the original NCBO Annotator for English text via a dedicated proxy that extends the original functionality. In this paper, we present a preliminary performance evaluation of the generic annotation web service (i.e., not specifically customized) for coding death certificates i.e., annotating with ICD-10 codes. This evaluation is done against the CépiDC/CDC CLEF eHealth 2017 task 1 manually annotated corpus. For this purpose, we have built custom SKOS vocabularies from the CéPIDC/CDC dictionaries as well as training and development corpora, for all three tasks using a most frequent code heuristic to assign ambiguous labels. We then submitted the vocabularies to the NCBO and SIFR BioPortal and used the annotation services on task 1 datasets. We obtained, for our best runs on each corpus the following results: English raw corpus (69.08% P, 51.37% R, 58,92% F1); French raw corpus (54.11% P, 48.00% R, 50,87% F1); French aligned corpus (50.63% P, 52.97% R, 51.77% F1).

Introduction

Biomedical data integration and semantic interoperability is necessary to enable translational research. The biomedical community has turned to ontologies and terminologies to describe their data and turn them into structured and formalized knowledge [START_REF] Blake | Bio-ontologies-fast and furious[END_REF][START_REF] Rubin | Biomedical ontologies: a functional perspective[END_REF]. Ontologies help to address the data integration problem by playing the role of common denominator. One way of using ontologies is by means of creating semantic annotations. An annotation is a link from an ontology term to a data element, indicating that the data element (e.g., article, experiment, clinical trial, medical record) refers to the term [START_REF] Uren | Semantic annotation for knowledge management: Requirements and a survey of the state of the art[END_REF]. When doing ontology-based indexing, we use these annotations to "bring together" the data elements from these resources.

The community has turned toward ontologies to design semantic indexes of data that leverage the medical knowledge for better information mining and retrieval. Despite a large adoption of English in science, a significant quantity of biomedical data uses the French language. Besides the existence of various English tools, there are considerably less terminologies and ontologies available in French [START_REF] Névéol | Language Resources for French in the Biomedical Domain[END_REF] and there is a strong lack of related tools and services to exploit them. This lack does not match the huge amount of biomedical data produced in French, especially in the clinical world (e.g., electronic health records).

In the context of the Semantic Indexing of French Biomedical Data Resources (SIFR) project, we have developed the SIFR BioPortal (http://bioportal. lirmm.fr) [START_REF] Jonquet | SIFR BioPortal : Un portail ouvert et générique d'ontologies et de terminologies biomédicales françaises au service de l'annotation sémantique[END_REF], an open platform to host French biomedical ontologies and terminologies based on the technology developed by the US National Center for Biomedical Ontology [START_REF] Noy | BioPortal: ontologies and integrated data resources at the click of a mouse[END_REF][START_REF] Whetzel | NCBO Technology: Powering semantically aware applications[END_REF]. The portal facilitates use and fostering of ontologies by offering a set of services such as search and browsing, mappings hosting and generation, metadata edition, versioning, visualization, recommendation, community feedback, etc. As of today, the portal contains 24 public ontologies and terminologies (+ 6 private ones) that cover multiple areas of biomedicine, such as the French versions of MeSH, MedDRA, ATC, ICD-10, or WHO-ART but also multilingual ontologies (for which only the French content is parsed) such as Rare Human Disease Ontology, OntoPneumo or Ontology of Nuclear Toxicity.

The SIFR BioPortal includes the SIFR Annotator1 a publicly accessible and easily usable ontology-based annotation tool to process text data in French. This service is originally based on the NCBO Annotator [START_REF] Jonquet | The Open Biomedical Annotator[END_REF], a web service allowing scientists to utilize available biomedical ontologies for annotating their datasets automatically, but was significantly enhanced and customized for French. The annotator service processes raw textual descriptions and tags them with relevant biomedical ontology concepts and returns the annotations to the users in several formats such as JSON-LD, RDF or BRAT. A preliminary evaluation [START_REF] Jonquet | SIFR BioPortal : Un portail ouvert et générique d'ontologies et de terminologies biomédicales françaises au service de l'annotation sémantique[END_REF] showed the web service matches previously reported work in French in performance, while being public, functional and turned toward the semantic web standards. However, this evaluation precedes the CLEF eHealth French task series and was not satisfactory. We had the motivation of evaluating the annotation service on the Quaero and CépiDC corpora used in the CLEF eHealth 2015-2017 French text data annotation tasks.

The SIFR BioPortal also offers the possibility of querying the original NCBO Annotator for English text via a dedicated proxy that extends the original functionality. Thus, in this case, the +600 ontologies of the NCBO BioPortal2 may be used. This service, called the NCBO Annotator+3 , is querying the original NCBO Annotator while offering new functionalities by pre processing of the input text and/or post processing of the original results. For instance, we have implemented the scoring of the results for both the SIFR and NCBO Annotator+ thanks to that proxy architecture [START_REF] Melzi | Scoring semantic annotations returned by the NCBO Annotator[END_REF]. Despite its wide and various uses and multiple evaluations, the NCBO Annotator has never been evaluated in the context of the CLEF eHealth tasks, and we believed it would be appropriate and relevant for the community to offer such an evaluation.

In this paper, we present our participation to the task 1 of the CLEF eHealth 2017 challenge, which tackles the problem of information extraction (diagnostic coding) in written clinical texts (death certificates). The objective of the task is to annotate each line of several death certificates, provided by the French Centre d'épidémiologie sur les causes médicales décès,(CépiDC) with an International Classification of Diseases, 10th revision (ICD-10) diagnostic code (French aligned task) or to annotate each document with the set of relevant ICD-10 diagnostic codes (French raw and English raw tasks). Considering that ICD-10 was never conceived to be used by automatic lexical tools, annotating the CépiDC data using only ICD-10 as source dictionary would have offered poor results, therefore, we have built custom SKOS vocabularies from the CépiDC/CDC dictionaries as well as the development and training corpora provided in the CLEF eHealth 2017 task 1 datasets. In the following, we will describe the construction of these custom vocabularies and present the results obtained both by the SIFR and NCBO Annotators used without any specific customization for the CLEF eHealth 2017 task 1. We obtained, for our best runs on each corpus, the following results: French Aligned (50.63% P, 52.97% R, 51.77% F1); French Raw (54.11% P, 48.00% R, 50,87% F1); English raw (69.08% P, 51.37% R, 58,92% F1). We will discuss the advantages and limitations of the annotators and possible perspectives for enhancing the performance of the specific task of coding death certificates or clinical notes. To us, in addition to technical performance (i.e., precision and recall) there are other aspects of the services that we think are crucial if we want to make the use of ontologies for annotation of clinical data mainstream. For instances, interoperability, ease of use as a service, openness, adoption of semantic web. A good annotation service shall be used in research or clinical environments, without any explicit knowledge of the technologies, the ontologies or the natural languages processing techniques involved.

Materials and methods

SIFR BioPortal and SIFR Annotator

The SIFR Annotator workflow is composed of several steps (figure to come): dictionary creation from ontologies, text pre-processing, concept recognition, semantic expansion (with mappings and hierarchy), annotations post-processing. For instance, in the final step, annotations are scored according to the context from which they have been generated, which is a requirement when they are used to index the original data. As another example, the SIFR Annotator can recognize negation, experiencer and temporality based on a customized French implementation of the NegEx/Context method [START_REF] Harkema | Context: an algorithm for determining negation, experiencer, and temporal status from clinical reports[END_REF]. Only the concept recognition step is evaluated in the context of the CLEF eHealth 2017 task 1, therefore, we will not describe into more detail the rest of the SIFR Annotator workflow here. For a presentation of the original NCBO Annotator service we point the readers to [START_REF] Jonquet | The Open Biomedical Annotator[END_REF][START_REF] Shah | Comparison of concept recognizers for building the Open Biomedical Annotator[END_REF].

When calling the SIFR Annotator (Figure 1), the user's free text is given as input to a concept recognition tool along with a dictionary. The dictionary is a list of strings that identifies concepts, built out of any knowledge artifacts uploaded in the SIFR BioPortal (ontologies, terminologies, vocabularies, dictionaries). The dictionary is constructed by accessing these artifacts and pooling all string forms, such as preferred names and synonyms that syntactically identify concepts. The SIFR Annotator uses all the French ontologies and terminologies available in the SIFR BioPortal which give us a dictionary of 255K concepts and around twice that number of terms. Enabling the service to use another ontology is as simple as uploading the new ontology into the portal and the backend dictionary will be automatically regenerated.

The concept recognizer uses the complete dictionary for annotation, but users can filter out results to some specific ontologies depending of the type of biomedical data the service is used to annotate. The SIFR Annotator and NCBO Annotator rely on a fast string matching algorithm called Mgrep [START_REF] Dai | An Efficient Solution for Mapping Free Text to Ontology Terms[END_REF]. Mgrep is UTF-8 compliant (since v4) and can then be used with data in other languages than English. Mgrep and/or the NCBO Annotator have been evaluated multiple times [START_REF] Twigger | Using the NCBO Web Services for Concept Recognition and Ontology Annotation of Expression Datasets[END_REF][START_REF] Sarkar | Leveraging Biomedical Ontologies and Annotation Services to Organize Microbiome Data from Mammalian Hosts[END_REF][START_REF] Shah | Comparison of concept recognizers for building the Open Biomedical Annotator[END_REF][START_REF] Groza | Using silver and semi-gold standard corpora to compare open named entity recognisers[END_REF][START_REF] Funk | Large-scale biomedical concept recognition: an evaluation of current automatic annotators and their parameters[END_REF] on different datasets an usually perform very well on precision e.g., 95% in recognizing disease names [START_REF] Xuan | Interactive Medline Search Engine Utilizing Biomedical Concepts and Data Integration[END_REF]. However, we do not know any specific evaluation of Mgrep performance on French. Mgrep can be parametrized (so can the SIFR Annotator) to match longest word only or all matches. It can also match partial part of the term in the dictionary. For a comparative evaluation of MetaMap [START_REF] Aronson | Effective mapping of biomedical text to the UMLS Metathesaurus: the MetaMap program[END_REF] and Mgrep done when building the NCBO Annotator the reader may refer to [START_REF] Shah | Comparison of concept recognizers for building the Open Biomedical Annotator[END_REF]. Mgrep does not execute any natural language processing techniques such as lemmatization, stemming, spellchecking, or detection of morphological variants, but offers a fast and reliable (good precision) matching that enables use of the software in a web service environment. We therefore rely on the creation of the dictionary to augment the recall by adding alternate syntactic form or variants susceptible to be found in the text. For instance, the SIFR Annotator includes now a lemmatize mode (beta, not used within CLEF eHeath 2017 task 1) that will lemmatize the original input before sending it to Mgrep which then also uses a lemmatized dictionary. Annotations performed with the SIFR Annotator can either be kept one by one with offset positioning of the matching term in the original given text, or can be aggregated (if multiple annotations with the same concepts occur in the given text) and scored in order to be used for instance to index the original data [START_REF] Jonquet | NCBO Resource Index: Ontology-Based Search and Mining of Biomedical Resources[END_REF]. An annotation (i.e., in essence, the URI of an identified concept) is always described with contextual information describing whether the annotation is direct or semantically expanded, if the match was done on a preferred name or synonym or if the identified concept is for instance negated. Neither scoring nor context information aspects are used in the CLEF eHealth 2017 task 1 settings. An important aspect for the SIFR Annotator is to be available as a web service. The service results may be described in multiple syntax (XML or JSON-LD) and format (e.g., RDF/XML described with the Annotation Ontology or BRAT). A specific CLEF eHealth output format has been also implemented to evaluate the service against the previous campaigns. For testing and ontology selection purposes, the web application user interface is available (Figure 1), however, the service is meant to be used through the REST application programming interface.

Note that thanks to a Docker (www.docker.com) packaging the SIFR BioPortal and Annotator may easily be installed locally to process sensitive data in-house, a common requirement when manipulating clinical data. All the code is open source and available on GitHub (https://github.com/sifrproject).

Within the SIFR project, we also developed an enhanced version of the NCBO Annotator to annotate English biomedical text data, without having to serve English ontologies locally. The NCBO Annotator+ uses a proxy service architecture that enhances the capabilities of the original annotation service by encapsulating around the original application programming interface. For instance, our recent implementations done for the French annotator are available, thanks to that proxy architecture, also for English e.g., scoring of annotations [START_REF] Melzi | Scoring semantic annotations returned by the NCBO Annotator[END_REF] or more recently detection of negation.

For CLEF eHealth 2017 task 1, we have used the SIFR and NCBO Annotators "as it is" without any specific customization for the task nor any training on the data. The runs have been executed with longest only parameter on, and without semantic expansion of the annotations, scoring or contextualization.

Task and corpus

The objective of CLEF eHealth 2017 task 1 is to annotate death certificates with ICD-10 codes both in French and in American English. For English, a corpus of death certificates from the CDC was provided, separated in a training and a test corpus. The training corpus contains 13,329 death certificates, for a total of 32,714 lines. The test corpus contains 6,665 certificates containing a total of 14,834 lines. For French, a corpus of death certificates from CépiDC was provided. More specifically, there was a training corpus that contained 65,844 documents and 195,204 lines, a development corpus with 27,851 document and 80,900 lines and a test corpus with 31,683 documents and 91,954 lines. The corpora are digitized versions of actual death certificates filled in by clinicians. Although the punctuation is not always correct or present, the corpus is already segmented in lines (as per the standard international death certificate model) which for the most part contains single sentences.

The French corpus was provided in both an aligned and a raw format, while the English corpus was only provided in the raw format. The raw format provides two files, a CausesBrutes file and an Ident file. The former contains semicolon separated values for the Document identifier (DocID), the year the certificated was coded (YearCoded), the line identifier (LineID), the raw text as it appears in the certificate (RawText), an interval type during which the condition occurred (IntType -seconds, minutes, hours, weeks, years) and an interval value (IntValue). The Ident file contains a document identifier, the year the certificate was coded, the gender of the person, the code for the primary cause of death, the age and the location of death. The aligned format is a reconciliation between the CausesBrutes and Ident files, where the fields have been aligned at the document and line number level. Thus, the aligned file contains the same unique fields that the original ones to which an extra field is added in the gold standard dataset providing a standardized text that represents the manually annotated code.

For CLEF eHealth 2017 task 1, we have used only the "RawText" information of both the aligned and raw datasets. We did not use any other information/features such as age or gender contained in the files.

Dictionaries construction

SIFR BioPortal already contained the French ICD-104 (CIM-10) reference terminology. This OWL version was originally produced by the CISMeF team from an automatic export from the HeTOP ontology/terminology server [START_REF] Grosjean | Multiterminology cross-lingual model to create the European Health Terminology/Ontology Portal[END_REF]. Respectively, the NCBO BioPortal already contained the English ICD-10. 5 This RDF version was automatically exported from the Unified Medical Language System (UMLS) with the umls2rdf tool. 6 However, the purpose of ICD-10 is to serve as a general purpose reference to code medical acts, and not to be directly used for text annotation and, especially not in a particular clinical task such as death certificate coding. Indeed, from our experiments, using ICD-10 classification alone for annotation leads to a F1 score below 10%.

For the French tasks, a set of dictionaries was provided by CépiDC that give a standardized description text of each of the codes that appear in the corpora. Additionally, the data from the aligned corpus (French only) could also be used to enrich the lexical terms of ICD-10. A similar dictionary was provided for the English task. In order to use these dictionaries within the SIFR and NCBO Annotator, we had to encode them using a format accepted as input within the portal, which includes RDFS, OWL, SKOS, OBO or RRF (UMLS format). In this case, the ideal choice in terms of standardization, potential reusability and simplicity was to use SKOS (Simple Knowledge Organization System) a W3C Recommendation specialized for vocabularies and thesaurus. For CLEF eHealth 2017 task 1, we produced two groups of SKOS dictionaries: CIM-10DC* for French, based on the French dictionaries and aligned corpus; ICD-10-CDC* for English based on the CDC corpus dictionary alone.

We set out in this construction process by first defining the appropriate schema to represent the SKOS dictionaries. We chose to use the same URIs as concepts identifiers for skos:Concept that the owl:Class in the available CIM-10/ICD-10 which allows our dictionaries to be fully aligned ontologically speaking with the original terminologies they enrich. Each of the codes was represented by a skos:Concept. The URIs are composed of a base URI and a class identifier that represents the ICD codes, in the following format: "[A-Z][0-9][0-9] ?[0-9]?" (e.g. G12.1 or A10). The identifier is slightly different from the codes from the task dictionaries: there is a dot before the last digit and if the last digit is zero, then the dot and the last zero are omitted. Thus, G12.1 in CIM-10 corresponds to G121 in the corpus while A10 in CIM-10 corresponds to A100 in the corpus. The corresponding URI in CIM-10 and this in CIM-10DC are: http://chu-rouen.fr/ cismef/CIM-10#G12.1, where http://chu-rouen.fr/cismef/CIM-10# is the base URI and G12.1 the code identifier. In ICD-10 and ICD-10CDC the URIs are like so: http://purl.bioontology.org/ontology/ICD-10/P08.0, where the base URI is http://purl.bioontology.org/ontology/ICD-10/ and the code identifier is P080.

When building the SKOS dictionaries, we used the same chapter hierarchy as ICD-10, although we kept only the chapter level of the hierarchy. This was mainly done for convenient browsing and visualization of the dictionaries in the NCBO and SIFR BioPortal. Each code concept was attached below the corresponding chapter concept (e.g. I98.5 belongs to the chapter I9.00) with the skos:broader property.

Construction algorithm

We built the French SKOS dictionary from the aligned corpus and all the CépiDC dictionaries. We built the English one only from the raw corpus and the CDC dictionary. We first built a code index, that to each code associated the list of labels retrieved from:

-The DiagnosisText field in the dictionary, associated to codes through the ICD1 and ICD2 fields. For French, we used a concatenation of all the dictionaries and for English we used the one dictionary file provided. -The RawText and StandardText (only for French) fields from the corpus associated to codes through the ICD-10 field in the corpus (AlignedCauses 2013Full for French, CausesCalculees EN training for English).

For each code concept the CépiDC and CDC dictionaries contained multiple labels. In order to follow SKOS specification, we had to select a preferred name automatically (skos:prefLabel) and assign the other labels as alternative labels (skos:altLabel). Note that this selection would note influence the annotation process as both preferred name and synonyms are included in the concept recognizer dictionaries. The selection heuristic took the shortest label that does not contain three or more consecutive capital letter (likely and acronym).

Ambiguous label selection heuristics An important issue when building the SKOS dictionaries was to assign ambiguous labels (i.e., identical labels which correspond to different codes). Indeed, those labels create ambiguity in the annotations and leads to better recall at the price of a low precision. For example, the label "choc septique" was present as preferred label or synonyms for 58 different codes. Therefore, we had to implement a selection heuristic to determine the most suitable code to which the label should be bound.

When using both the standard text and the raw text fields from the corpus, if standard text label is ambiguous, a simple heuristic is to not add it to any code but just use the raw text instead. Given that the raw text is unique, the ambiguity related to the inclusion of the test corpus is removed. We called this first strategy "Adaptive dictionary generation" and created a CIM-10DCA French SKOS dictionary to evaluate it. Given that this strategy relied on the availability of a standardized text, it was confined to the French aligned task, as the raw English corpus contained no standard labels.

The drawback with the previous heuristic is that we lose some labels that would otherwise have potentially increased recall. Thus, we searched a way of assigning ambiguous labels to one code only. Taking inspiration from the idea of the most frequent sense baseline often used in Word Sense Disambiguation tasks, we adopted a heuristic that assigns ambiguous labels to the most frequent code only. We use the training corpus to estimate the frequencies of use of the codes (gold standard annotations) so that when a label can belong to several codes, we can sort the codes by frequency and chose either the most frequent code (MFC) or the top k most frequent codes (kMFC).

In practice the "Adaptive" strategy led to a much lower recall without particularly improving precision. Final F1 scores were worse than with the MFC strategy which led to a precision and recall that were balanced. This is the strategy we have finally used in the reported results.

Availability of the SKOS dictionaries

The final SKOS dictionaries built with the best ambiguous label strategy have been uploaded respectively on the SIFR and NCBO BioPortal, and are accessible in private mode only for now (access upon request, an account is required):

-CIM-10DC-ALL contains 6817 concepts for a total of 295,385 labels.

-CIM-10DC-ALLMFC contains the same number of concepts but only 249,524 labels. -ICD-10CDC contains 3738 concepts with 166,500 labels.

We have also created a resource solely from the CépiDC dictionaries (without using the corpus) called CIM-10DCD. This one do not contain any sentence originally present in death certificates. We are currently discussing with the CépiDC, potential public releases of the SKOS dictionaries as well as the workflow to update them on a regular basis. Indeed, we believe it is also part of the SIFR project mission to facilitate open access to resources (and adopting standard ways of describing them e.g., semantic web standards), when licensing permits.

ICD-10/CIM-10 Coding with ontology concepts

Given that we used the SIFR and NCBO Annotators, besides manually curating the created SKOS dictionaries, the final step to obtaining a working system for the task was to write a complete workflow to: 7 1. Read the corpus in the raw or aligned formats; 2. Send the text to the Annotators REST API with the right ontologies and annotation parameters; 3. Retrieve the annotations produced by the Annotators; 4. Optionally prune some annotations (post-annotation heuristic); 5. Produce the output in the right raw or aligned format.

We implemented two post-annotation heuristics:

-Most Frequent Code, if a particular line was annotated with several codes, only keep the most frequent code based on the code distribution of the training corpus. There are no parameters. -Code Frequency Cutoff, we calculate a normalized probability distribution of the codes that annotate a particular line (with a density function in the [0, 1] range) and only keep the codes below a cumulative probability threshold. The only parameter is the cut-off threshold.

The parameters of the entire system are the combination of the parameters of NCBO or SIFR annotator (list of ontologies, longest match (T/F), expand mappings (T/F)) with any post-annotation heuristic parameter.

Reproducibility

Using the SIFR annotator is as simple as sending a request through the HTTP REST API, for example to annotate the sentence: "Absence de tumeur maligne" with the French version of WHO-ART and MedDRA, it can be done with: 8http://services.bioportal.lirmm.fr/annotator/?text=Absence%20de% 20tumeur%20maligne&negation=true&ontologies=WHO-ARTFRE,MDRFRE

Because of the sensitive nature of the CépiDC data, we have used a local version of the NCBO and NCBO Annotators in order to avoid sending the data out on the network. However, to reproduce our results one would require to have access to the private SKOS dictionaries on the NCBO and SIFR BioPortal and in that case, use the user interface or the REST web service API. The reproduction instructions are available here: https://twktheainur.github.io/ bpannotatoreval/LIRMMCLEF2017Task1Instructions.html

Results

Using the previously described workflow, we have performed six runs:

French Run 1 (Aligned and Raw): Annotation with longest only parameter on and running on a local instance of the SIFR Annotator with CIM-10 and CIM-10DC-ALLMFC as target resources. French Run 2 (Aligned and Raw): A fallback strategy starting from the result file of Run 1, and, for each line without any annotations, takes the annotations from a second run, which used CIM-10 and CIM-10DC-ALL as target resources. This is, in essence a late fusion technique, that aims at increasing the recall, without sacrificing precision.

English Run 1 (Raw): Annotation with longest only parameter on and running on a local instance of NCBO Annotator with ICD-10 and ICD-10CDC as target resources. English Run 2 (Raw): Same as Run 1 but with ICD-10CM as additional target (also available in the NCBO BioPortal): the Clinical Modification of ICD-10 made in the USA for the classification of morbidity causes.

English raw results

11 teams participated to the English raw evaluation. Table 1 presents the results obtained by our two runs against the average and median results the runs submitted to this task. The NCBO Annotator obtained results that are exactly the median value of all the results submitted (all causes). We can measure a slight decrease in precision and increase in recall with the introduction of ICD-10-CM in Run 2. Regarding the external causes, the NCBO Annotator obtains a better precision and f-measure than the average and median results submitted to the challenge.

French raw and aligned results

13 runs have been submitted by 9 teams to the French raw evaluation. 7 runs have been submitted by 5 teams to the French aligned evaluation. Tables 2 and3 present the results obtained by our two runs against the average and median results of the runs submitted to this task. As expected, the SIFR Annotator did perform similarly on the raw and aligned datasets (as they were processed exactly with the same workflow). The results are exactly the median value of all the results with the raw dataset, but slightly under the median value for the aligned datasets (all causes). Indeed, teams that have used other information from the aligned dataset probably performed better than the SIFR Annotator here. Regarding the external causes, we obtain better precision and F1 than the average and median results submitted to the challenge.

Discussion

The results obtained are in line with what could be expected from our approach, which really is an evaluation of how the SIFR and NCBO Annotators concept recognition component works. The simple string matching approach adopted by Mgrep generally offers a good precision (around 80%) if the ontology is properly lexicalized and concretely captures the terms used in the text to annotate. For CLEF eHealth 2017 task 1, the loss in precision is explained by the nature of the dictionaries used as a source to produce our terminology: a same label can correspond to several different classes (here ICD10 codes). This practice is usually strongly avoided when designing ontologies as it inevitably creates ambiguities. Concerning recall, our performance is also limited since the concept recognizer does not include any natural language processing techniques that would increase the amount of matches, handle morphological variants (as simple as plural forms) or any other alternative concepts. All phenomena that are common in reality but not captured as synonyms by the source ontologies will not be recognized properly. Previous evaluation of the NCBO Annotator [START_REF] Shah | Comparison of concept recognizers for building the Open Biomedical Annotator[END_REF] already identified such limitations. Unsurprisingly, we found the same limitations apply to the French version. These issues are particularly important when using resources such as ICD10 that are not designed to be automatically used for annotation (in spite of it's original mission that is indeed coding medical acts).

The purpose of the SIFR Annotator, as the NCBO Annotator when released in 2009, was not to beat state-of-the-art systems tuned for specific tasks. The concrete advantages of the services, both respectively connected to the SIFR and NCBO BioPortal come from: (i) the size and variety of their dictionaries coming from ontologies, (ii) their availability as a web service that can be easily connected in any semantic indexing workflow, and finally (iii) their adoption of a semantic web vision that strongly encourages returning URIs that can then reused to facilitate data integration and semantic interoperability. One should also note that the semantic expansion step (which uses the mappings between ontologies and the is a hierarchies to generate additional annotations) as well as the post-processing of the annotations (which scores and contextualizes the annotations) are interesting features not evaluated within CLEF eHealth 2017 task 1.

Despite of their limitations, the NCBO and SIFR Annotators obtained exactly median results when compared to the performance of all the participating systems. Therefore, considering the other discussed advantages, we believe they are two services that can help in a wide class of text mining or annotation problems, but of course not for all. It is important to note the systems were not tailored for this task and their performance will highly vary depending of the data to annotate and the ontologies targeted.

Participation in CLEF eHealth 2017 task 1 is, however, a very good manner of enabling us to improve our SIFR Annotator and potentially the NCBO Annotator also. Such improvements shall be either generic (changes to the overall workflow, independent of task) or tailored for improving the results to the CLEF eHealth series (Quaero or CépiDC corpora). In order to better understand the shortcoming of the system, we sampled 100 false positives and false negatives from the best runs of the SIFR Annotator on the French aligned development dataset and proceeded to manually determine the case of the error. Some class of errors are as follows:

-Errors because of missing synonyms. A few good illustrative examples include:

• The code R09.2 "arrêt respiratoire" was not identified within the text "arrêt cardio respiratoire" or "détresse cardiorespiratoire." • The code J96.0 "insuffisance respiratoire aiguë" was not identified within the text "détresse respiratoire." Although some of these false negative could be avoided with a richer dictionary (1st case) or simple synonym generation (2nd case), we found some that strongly relies on some medical expertise that can hardly be captured by a dictionary based approach (maybe by a machine learning one, assuming there is enough data to train the tool).

-Single match returned whereas a multiple match was expected. Indeed, the MFC strategy resulted in assigning the synonyms to only one code in CIM-10-DC therefore, when for the same text, several annotations where expected, we found only one. For instance, the code G40.9 "épilepsie, sans précision" was found with the text "epilepsie avec etat de mal" but not the code G41.9 "état de mal épileptique, sans précision." Note that those errors are only present with the MFC strategy.

-Morphosyntactic or lexical variation (e.g., accent, dash, comma, spelling). For instance, the code J18.9 "emphysème, sans précision" was not identified within the text "emphysème pumonaire secodaire tabagisme actif" because of the spelling of "pulmonaire." -Annotations were made with a more general (i.e., parent in ICD-10 hierarchy), often because of a partial match within an expression. -Errors because the annotation would require to use other explicit information in the certificate or medical knowledge. For instance, the annotation with code I10 "hypertension essentielle (primitive)" was not found from the text "TC suite à une chute avec épilepsie séquellaire et tr cognitifs" as it was annotated within the corpus. Or the code R68.8 "autres symptômes et signes généraux précisés" was not identified within the text "atteinte polyviscérale diffuse."

From this review of the pitfalls of the SIFR Annotator on the CépiDC corpus, and from other in-house experiments, we clearly identified the need to improve the dictionary generation process when extracting the labels from the source ontologies. This is the moment where the terms shall be enriched adding other alternative synonyms or morphosyntactic or lexical variations. However, this shall be done with precautions to be sure to augment recall without decreasing precision as the introduction of new ambiguity shall be avoided.

Another potential important source of improvement for the SIFR Annotator shall come from generating and curating alignments between ontologies. For instance, on the CépiDC corpus, when used with other ontologies the SIFR Annotator was able to identify unambiguous concepts from other ontologies. The system is implemented to use the mappings between ontologies to expand the original direct annotations made from the text, but of course this suppose the mappings have been generated and uploaded to the SIFR BioPortal. In the case of ICD10, there exists multiple source of published mappings that we plan to upload in the future. This will clearly have an effect on recall.

The limitations on one annotation scenario shall not be the same on another scenario. We are currently evaluating the performance of the SIFR Annotator on the Quaero corpus [START_REF] Névéol | The QUAERO French medical corpus: A ressource for medical entity recognition and normalization[END_REF] used during previous editions of CLEF eHealth and we identified other problems such as ambiguity (as we use several ontologies whereas Quaero is annotated with unique UMLS Metathesaurus concepts) or missing translated terms (as the Quaero corpus used English UMLS concept when French ones were not available thus inevitably disadvantaging methods that would not use some kind of translation approach). Overall, despite of these limitations, our results on the Quaero corpus varies between 63 and 70% F1 on plain entity recognition (UMLS semantic groups) and 36-37% F1 on normalized entity recognition (UMLS concept unique identifiers) on the EMEA dataset. And respectively 58-69% F1 and 32-33% the Medline dataset. These results put the SIFR Annotator among the top systems for plain entity and in the first half for normalized entity (while not using automatic translation!). Better Quaero results analysis and reporting shall be the subject of another specific future communication.

We would also like to point to some recent improvements that we have made to the SIFR Annotator that are currently under evaluation. When annotating clinical notes with medical conditions, it is important to filter out negated conditions and distinguish present conditions from antecedents or conditions experienced by someone other than the patient. For this reason, several methods have been proposed to detect the context of already identified clinical conditions, especially for English medical text. The English-language system, NegEx/ConText, is one of the best and fastest algorithms for the determination of the context of medical conditions [START_REF] Harkema | Context: an algorithm for determining negation, experiencer, and temporal status from clinical reports[END_REF]. ConText is based on lexical cues (trigger terms) that modify the status of medical conditions appearing in the scope of the cues. We have adapted this system to the French language. Our approach consisted in compiling an extensive list of French lexical cues by a process of automatic and manual translation and enrichment. Then, we interconnected the NegEx/ConText program with the NCBO and SIFR Annotators thanks to the proxy architecture previously mentioned. This feature can already be used on the SIFR BioPortal for the French and English annotation services. Our first evaluation confirms the ability to detect negation with a very high F1 score, slightly improving previous published work done in the past to adapt NegEx for French. This study shall also be part of another specific future communication on the SIFR Annotator. Due to time limitation, we have not use NegEx/ConText on the CépiDC corpus although we are not sure about the impact of this feature on the results.

Conclusions

In this paper, we presented our participation to the task 1 of the CLEF eHealth 2017 challenge using the NCBO and SIFR Annotators. Our results are encouraging: around 50-60% of F1 score means that more than half of the task of coding death certificates with ICD-10 codes can be automatized. Especially considering that we have not implemented anything specific to process these data. But of course, we will have to improve these results to be among the best performing systems. Some improvements perspectives have been discussed.

We have also argued in this paper that according to us the technical performance (F1) shall not be the only argument in evaluating a semantic annotation tool. The SIFR project has invested a significant amount of effort in order to offer a generic, open and quite robust platform that could easily be used "at the click of the mouse" to annotate biomedical text data and access French biomedical ontologies and terminologies. Someone can upload a new resource to the SIFR BioPortal and get a dedicated annotation service, interconnected to other existing ontologies, in a couple of hours.

Indeed, the SIFR Annotator is different from other related tool in French biomedical text mining as: (i) it is a dynamic web service with JSON-LD outputs which can be integrated in current programmatic workflows; (ii) it uses public ontologies both to create annotations and to expand them; (iii) it has access to one of the largest available sets of publicly available biomedical ontologies in French. We believe the SIFR Annotator can therefore be used in a large span of biomedical applications including annotating clinical text data. We are currently using the service in the context of the French PractiKPharma project (http://practikpharma.loria.fr) which aims to validate pharmacogenomics state-of-the-art knowledge on the basis of practice-based evidences, i.e., knowledge extracted from electronic health records.

Fig. 1 :

 1 Fig. 1: Annotator interface in the SIFR BioPortal. The text is here annotated with Mesh and CIM-10 (ICD10), with negation and longest only parameters.

Table 1 :

 1 Results on the English raw dataset

			All Causes			External Causes
		Precision (%) Recall (%) F1 (%)	Precision (%) Recall (%) F1 (%)
	Run1	69.1	51.4	58.9	23.2	52.4	32.2
	Run2	64.6	52.7	58.0	23.3	52.4	32.3
	Average 67.0	58.2	62.2	40.5	26.7	26.1
	Median 64.6	60.6	61.1	27.9	26.2	27.4

Table 2 :

 2 Results on the French raw dataset

			All Causes			External Causes
		Precision (%) Recall (%) F1 (%)	Precision (%) Recall (%) F1 (%)
	Run1	54.1	48.0	50.9	44.3	36.7	40.1
	Run2	54.0	48.0	50.8	44.3	36.7	40.1
	Average 47.5	35.8	40.6	36.7	24.7	29.2
	Median 54.1	41.4	50.8	44.3	28.3	37.6

Table 3 :

 3 on the French aligned dataset

			All Causes			External Causes
		Precision (%) Recall (%) F1 (%)	Precision (%) Recall (%) F1 (%)
	Run1	50.6	53.0	51.8	41.2	40.3	40.7
	Run2	50.5	53.0	51.7	41.2	40.3	40.7
	Average 64.8	55.6	59.3	50.5	31.9	36.6
	Median 62.9	54.0	54.8	50.8	33.3	40.6

http://bioportal.lirmm.fr/annotator

http://bioportal.bioontology.org

http://bioportal.lirmm.fr/ncbo_annotatorplus

http://bioportal.lirmm.fr/ontologies/CIM-10

https://bioportal.bioontology.org/ontologies/ICD-10

https://github.com/ncbo/umls2rdf

The REST API requires an APIkey to be used (obtained by creating an account on the portal). In that example, one can use the demo API key and add &apikey=c34b7653-0639-4946-81af-8ac76fe809dd at the end of the call.

Acknowledgements

This work is supported by the French National Research Agency within the PractiKPharma (grant ANR-15-CE23-0028) and SIFR (grant ANR-12-JS02-01001) projects as well as by the European H2020 Marie Curie actions (grant 701771), the University of Montpellier and the CNRS. We also thanks the US National Center for Biomedical Ontology for their assistance with the NCBO Annotator and the CLEF eHealth 2017 organizers for their help.