Houssam-Eddine Gougam

Audine Subias

Yannick Pencolé

Discriminability Analysis of Supervision Patterns by Net Unfoldings

Keywords: discriminability, diagnosability, supervision patterns, labeled Petri nets, Petri nets unfolding

In this paper, we are interested in the discriminability of supervision patterns, in discrete event systems (DES). Discriminability -as opposed to diagnosability -is the possibility to detect the exclusive occurrence of a particular behavior of interest -called the supervision pattern. To this end, we propose to adapt the classical twin-plant approach to Petri nets unfolding. The usage of unfoldings permits us to avoid the combinatorial explosion associated with marking graphs. The method can also be used to solve the classical problem of discrete event systems' diagnosability.

INTRODUCTION

In the context of discrete-event systems (DES), the supervision task consists in analyzing the sequence of observed events and determining whether an abnormal/faulty situation has occurred before deciding what kind of actions to perform in order to recover the optimal performance of the system. By the intrinsic nature of DES, an abnormal situation is characterized by a partial order of observable/nonobservable events called an event pattern or a supervision pattern as introduced in [START_REF] Jéron | Supervision Patterns in Discrete Event Systems Diagnosis[END_REF].

In this paper, we address the problem of analysing the discriminability of a set of supervision patterns. Two supervision patterns R 1 and R 2 are discriminable if it is always possible to assert from the observed events that if R 1 (resp. R 2 ) has occurred then R 2 (resp. R 1 ) has not occurred and will not occur.

The notion of pattern discriminability is obviously related to the notion of pattern diagnosability and their respective analyses [START_REF] Jiang | Diagnosis of repeated/intermittent failures in discrete event systems[END_REF], [START_REF] Jéron | Supervision Patterns in Discrete Event Systems Diagnosis[END_REF], [START_REF] Yoo | Diagnosis of behaviors of interest in partially-observed discrete-event systems[END_REF], [START_REF] Gougam | Supervision patterns: Formal diagnosability checking by petri net unfolding[END_REF]), however the point of view is di erent. The result of a diagnosability analysis states whether any considered pattern is always detectable or not. If such a property holds then it is possible to design a diagnoser that will always be able to determinate which patterns have occurred in a finite amount of time. However there is a pitfall: underlying real-world systems are not and cannot be diagnosable as the diagnosability property is very restrictive [START_REF] Pencolé | Assistance for the design of a diagnosable component-based system[END_REF]) and requires an observability level that cannot be implemented as a set of sensors on the underlying system (physical and/or cost constraints). The classical diagnosability analyses will then conclude such a real-world system is not diagnosable, so what is next?

To cope with this problem, we propose to develop a more constructive analysis by checking the discriminability of the occurrence of a set of patterns with respect to another disjoint set of patterns. The analysis is constructive in the sense that any partial discriminability result has an outcome that can impact the design of a diagnoser for the analysed system even if the underlying system is not globally diagnosable. And finally, once the proposed discriminability analysis is completed, checking the classical diagnosability analysis is straightforward and for free.

In our proposal, the development of the discriminability analysis relies on two original choices. The first one is the use of Petri net -which were shown to be more appropriate to solve diagnosis problems [START_REF] Lai | A comparison between two diagnostic tools based on automata and petri nets[END_REF] to model patterns as well as the system [START_REF] Basile | An ecient approach for online diagnosis of discrete event systems[END_REF], [START_REF] Dotoli | On-line fault detection in discrete event systems by petri nets and integer linear programming[END_REF]) so that we benefit of the natural way to represent event concurrency. The second one is the use of net unfoldings [START_REF] Mcmillan | A technique of state space search based on unfolding[END_REF], [START_REF] Esparza | An Improvement of McMillan's Unfolding Algorithm[END_REF], [START_REF] Benveniste | Diagnosis of asynchronous discrete-event systems: a net unfolding approach[END_REF]) in order to benefit of a representation as a partial order of events. Unfoldings avoid the explicit enumeration of event sequences that is performed by techniques based on marking graphs like in [START_REF] Cabasino | A new approach for diagnosability analysis of petri nets using verifier nets[END_REF]. Our proposed approach allows us to have some interesting properties. First, genericness, meaning that we do not impose particular patterns, we rather define a generic framework for supervision pattern, and every pattern falling in this framework can be used for supervision. Second, the supervision patterns are compact, i.e. only relevant events are included leading to more concise patterns. Finally, reusability, which is a direct consequence of the compactness, the exclusive use of relevant events yields supervision patterns which are independent from the system.

The paper is organized as follows. Section 2 introduces the problem, Section 3 presents Petri nets and their use to model the system and the patterns. The proposed analysis method is detailed in Sections 4 and 5. An example of our method is given in Section 6. Finally, we conclude in Section 7 and give some perspectives.

DISCRIMINABILITY OF SUPERVISION PATTERNS

Analyzing the discriminability of a system in the DES context means characterizing the performances of the diagnosis algorithm. A diagnosis algorithm, given an observable sequence produced by the system, is responsible of returning its state, i.e. is the system in a normal state or a faulty state, and in the latter case, whichfaulty -behavior yielded this state. If such algorithm exists, and can determine with certainty after a bounded number of observations that only a particular combination of behaviors occurred, this combination is said to be discriminable. On the other hand, if the algorithm can detect the occurrence of a behavior with no information about the possible occurrence of other faulty behaviors, the former is said to be detectable.

In this paper, we consider a system modeled by a language, faulty behaviors are recognized by supervision patterns which are also languages with specific properties. More formally, the problem of supervision pattern discriminability in discrete event systems is then defined in the following context.

Let À = {a, b, . . .} be a finite set called an alphabet. The Kleene closure of À denoted À ú is the set of finite sequences -or words -over À -including the empty sequence, denoted in the following by ⁄. À + = À ú \ {⁄} is the set of non-empty finite sequences. A subset S ™ À ú is called a language over À. The continuation z of a sequence w in S is a sequence such that wz oe S. So, the set of w's continuations in S is defined as S/w = {z oe À ú : wz oe S}. The classical projection of a sequence w oe À ú on a subset À p of À is denoted P Àp (w). Finally, ÎwÎ denotes the length of the sequence w. The behavior of the system is modeled by the prefix-closed language S over an alphabet À representing the set of events generated by the system. Some of these events are observable, while others are not. The observable events are represented by the set À o and the set of non-observable events is called À u . So, À = À o fi À u . We make the assumption that the system is À o -alive, meaning: 'w oe S, ÷z oe S/w : P Ào (z) " = ⁄; this hypothesis ensures that the system produces observations with some regularity. A supervision pattern R is a language over À R ™ À that recognizes R-faulty sequences.

Definition 1. Let R = {R 1 , R 2 , . . . , R n } be a set of supervision patterns. A sequence w oe À ú is said to be R i -faulty if: P ÀR i (w) oe R i . A sequence w oe À ú is said to be R-faulty if: 'R oe R : w is R-faulty. A sequence w oe À ú is said to be faulty if: ÷R oe R : w is R-faulty. Definition 2. Let R = {R 1 , R 2 , . . . , R n } be a set of supervision patterns. Let R s oe 2 R be a subset of R. A sequence w oe À ú is said to be exclusively R s -faulty in R if: ; 'R oe R s : w is R-faulty 'R " oe R s : w is not R-faulty
We will simply use "exclusively R s -faulty" rather than "exclusively R s -faulty in R" when there is no ambiguity.

We can now define the discriminability of a set of supervision patterns.

Definition 3. Given a system S and a set of supervision patterns R = {R 1 , R 2 , . . . , R n }. A subset R s of R is said to be discriminable if: ÷n oe N, 'w an exclusively R s -faulty word of S, 'z oe S/w : ÎP Ào (z)Î Ø n =∆ D where the discriminability condition D is:

'w o oe P ≠1 Ào (P Ào (wz)) : w o is exclusively R s -faulty This property insures that one can detect with certainty that only a particular combination of patterns -namely R s -occurred.

Similarly, we define the R-diagnosability of a system.

Definition 4. Let R = {R 1 , R 2 , . . . , R n } be a set of supervision patterns. A language S is R-diagnosable if: ('R oe R)(÷n oe N), 'w an R-faulty word of S, 'z oe S/w : ÎP Ào (z)Î Ø n =∆ D where the diagnosability condition D is: 'w o oe P ≠1 Ào (P Ào (wz)) : w o is R-faulty More intuitively, a language S is R-diagnosable if it
does not contain two arbitrary long sequences, the first R-faulty, the second non R-faulty, which have the same observable behavior.

ON MODELING ASPECTS

To tackle the problem of discriminability, we propose to use labeled Petri nets to model the system and the patterns.

Labeled Petri nets

Definition 5. A labeled Petri net is a tuple ÈP, T, A, ¸, L, ÀÍ where:

• P : a set of places; • T : a set of transitions with P fl T = ?;

• A ™ (P ◊ T ) fi (T ◊ P ): a binary relation representing arcs between nodes; • ¸: P fi T ae L fi À fi {⁄}: a labeling function where L is the set of place labels, À is the set of transition labels and ⁄ denotes the empty sequence. ¸is naturally extended to markings and sequences of nodes. Let M be a marking:

¸(M ) = {¸(p) : p oe M }. For s = s 1 s 2 . . . oe (P fi T ) ú , ¸(s) = ¸(s 1 )¸(s 2 ) . . ..
A marking M is a map from P to N which maps any place p to the number of tokens M (p) contained in it. For the sake of simplicity, a marking may sometimes be denoted as a multiset. For instance, let ≠ ae M , we can also write M 0 s ≠ ae M . Given a marked and labeled Petri net « and a set of final markings Q, the G-type language (see [START_REF] Peterson | Petri nets[END_REF]) generated by « is given by:

P = {p 1 , p 2 , p 3 }, the marking M such that M (p 1 ) = 2, M(p 2 ) = 0 and M (p 3 ) = 1 can be represented as M = {p 1 , p 1 , p 3 }. A marked
L(«) = {¸(s) : s oe T ú • M 0 s ≠ ae M • ÷M Õ oe Q, M Õ ™ M }.
The system is modeled by a Petri net «. As the language of the system is prefix-closed, it can be represented as the G-type language of a bounded Petri net (÷n oe N, 'p oe P : M (p) AE n) associated with the set of final markings Q = {?} (any reachable marking being a superset of ?).

Supervision Patterns

The classical framework of DES diagnosis [START_REF] Sampath | Diagnosability of discrete-event systems[END_REF]) relies on detecting the simple occurrence of particular -faulty -events. The supervision patterns framework, as proposed in [START_REF] Jiang | Diagnosis of repeated/intermittent failures in discrete event systems[END_REF] and in [START_REF] Jéron | Supervision Patterns in Discrete Event Systems Diagnosis[END_REF], extend this analysis to more complex models, enabling us to express more interesting behaviors, possibly involving several events. We propose to represent a supervision pattern as a labeled Petri net. The first condition ensures that every place is either labeled by N or F . Condition 2 states that in the initial state, each marked place is labeled by N . Condition 3 states that a place labeled N and another one labeled F can not be marked at the same time in a reachable marking, meaning that the pattern can not be recognized and not recognized at the same time. Condition 4 ensures that once the pattern is recognized -the place labeled F is markedit can not return to a non faulty marking. Condition 5 is the completeness condition: from any reachable marking, the supervision pattern can fire a transition labeled by any event in its alphabet, this condition ensures compact independent pattern (the pattern does not include other events than those relevant to faulty behavior).

Definition 6. A supervision pattern is a marked labeled Petri net ÈP, T, A, ¸, L, À, M 0 Í such that: (1) (labeling) L = {N, F }; (2) (initialization) 'p oe P : M 0 (p) > 0 ∆ ¸(p) = N ; (3) (exclusivity) 'p 1 , p 2 oe P : ¸(p 1 ) = N • ¸(p 2 ) = F ∆ M (p 1 ) ◊ M (p 2 ) = 0; (
Any supervision patterns is associated to the set of final markings Q that contain only one marking Q = {{p oe P :

¸(p) = F }}.
Example: event concurrency Let E = {e 1 , e 2 , . . . } be a set of events. The pattern describing the concurrent occurrence of these events is the labeled Petri net depicted in Figure 1, with the final marking Q = {{p 0 }}. Transition t 0 , as it is labeled with ⁄, is firable as soon as every event of E has occurred.

N N • • • N e 1 e 2 • • • e |E| N N • • • N e 1 e 2 e |E| ⁄ F e 1 e |E| • • • Figure 1. A set of concurrent events.

DISCRIMINABILITY ANALYSIS APPROACH

The problem of the discriminability of supervision patterns can now be redefined as being the analysis of the discriminability of a subset of supervision patterns modeled by labeled Petri nets s oe 2 where = {oe 1 , oe 2 , . . . , oe n } in a labeled Petri net « where À oei ™ À for all i.

Definition 7. A subset s oe 2 is discriminable in if L( s ) is discriminable in L( ).
Where: L( ) = {L(oe 1 ), L(oe 2 ), . . . , L(oe n )} One classical method used in analyzing the diagnosability of faults in a discrete event system -introduced in Yoo and Lafortune (2002) and [START_REF] Jiang | A polynomial algorithm for testing diagnosability of discrete event systems[END_REF], is the use of a twin-plant on the observable events to detect normal and faulty executions that share the same observable behavior -if any -and thus conclude about the non-diagnosability of the system by looking for such sequences that have infinite number of observable events. In the supervision pattern context, the same principle applies. But, first, the supervision patterns must be combined to form a metapattern recognizing all possible combinations of the patterns. Next, the recognition of this meta-pattern must be taken into account within the system «. These two operations are realized by two products.

Synchronized product of labeled Petri nets

Let « 1 = ÈP 1 , T 1 , A 1 , ¸1, L 1 , À 1 , M 10 Í and « 2 = ÈP 2 , T 2 , A 2 , ¸2, L 2 , À 2 , M 20 Í be two labeled Petri nets. The synchro- nized product « = « 1 Î « 2 is the labeled Petri net « = ÈP, T, A, ¸, L, À, M 0 Í such that: • P = P 1 fi P 2 ; • T = T1 fi T2 fi T s , where: Ti = {t oe T i : ¸i(t) " oe À 1 fl À 2 }, i = 1, 2; and T s = € loeÀ1flÀ2 {t 1 Î t 2 : ÷(t 1 , t 2 ) oe (T 1 ◊ T 2 ) : ¸1(t 1 ) = ¸2(t 2 ) = l}; • A = Â1 fi Â2 fi A s , Âi = A i \[(P i ◊(T i \ Ti ))fi((T i \ Ti )◊P i )], i =
; • ¸(t) = Y ] [ ¸1(t 1 ) if t = t 1 Î t 2 oe T s ¸1(t) if t oe T 1 ¸2(t) if t oe T 2 ; • L = L 1 fi L 2 ; • À = À 1 fi À 2 ; • M 0 (p) = ; M 10 (p) if p oe P 1 M 20 (p) if p oe P 2 .
This product can be constructed simply by taking the union of the two nets, removing transitions with labels in À 1 flÀ 2 , and for each (t 1 , t 2 ) oe T 1 ◊ T 2 where ¸(t 1 ) = ¸(t 2 ) " = ⁄, add a transition t 1 Î t 2 to the product inheriting their label and arcs.

The product imposes the simultaneous evolution of the two Petri nets, whenever a shared event occurs. In a general context, this can lead to a deadlock -the case where the first petri net needs to fire a synchronized transition while the second one did not reach the appropriate marking.

The completeness condition imposed on the supervision patterns ensures that this situation can not happen in our context -the completeness condition states that in any marking, the pattern can fire a transition with any label. So, applying this product on two supervision patterns can model all the possible combinations of their evolutiononly one of them evolves, the two evolve in the same time, etc.

Final Markings: Product of Patterns Let Q i be the set of final markings of oe i , i = 1, 2. We define the set of final markings of the product oe

= oe 1 Î oe 2 , Q = Q 1 fi Q 2 .
Proposition 8. L(oe) = {w oe (À 1 fi À 2 )

ú : P À1 (w) oe L(oe 1 ) ' P À2 (w) oe L(oe 2 )}. Proposition 9. w oe L(oe) ≈∆ ÷w 1 oe L(oe 1 ), P À1flÀ2 (w) = P À1flÀ2 (w 1 ) ' ÷w 2 oe L(oe 2 ) : P À1flÀ2 (w) = P À1flÀ2 (w 2 ).

Final Markings: Product of the System and a Pattern

The recognition of the supervision pattern must be taken into account within the system. This is realized by a slight modification of the product -more precisely, the final markings -which is applied to the pattern and the system. For clarity we will use a di erent symbol for this product ı.

Let Q i be the set of final markings of « i , i = 1, 2. We define the set of final markings of the product

« = « 1 ı « 2 , Q = {q = q 1 fi q 2 : (q 1 , q 2 ) oe Q 1 ◊ Q 2 }. Proposition 10. L(«) = {w oe (À 1 fi À 2 ) ú : P À1 (w) oe L(« 1 ) • P À2 (w) oe L(« 2 )}. Proposition 11. w oe L(«) ≈∆ ÷w 1 oe L(« 1 ), ÷w 2 oe L(« 2 ) : P À1flÀ1 (w) = P À1flÀ2 (w) = P À1flÀ2 (w 2 ).
From these propositions, we can characterize faulty sequences.

Proposition 12. Given a system « and a meta-pattern :

w oe L(«) is faulty ≈∆ w oe L(« ı ).
All necessary notations being introduced, the analysis method is detailed in the following.

Analysis stages

We define an "'" operator applicable to sequences, alphabets, and labeled Petri nets, which renames appropriately its operand by priming unobservable events and the label of each place. We also change the labels of every place in the supervision patterns oe i from N (reps. F ) to N i (resp.

F i ).
We start by combining the set of supervision patterns in a meta-pattern = (oe 1 Î oe 2 Î . . . Î oe n ) -the product is obviously associative -then we perform the product of « and to obtain « = « ı . The net ≈ is calculated as the synchronized product of « and « Õthe result of this product is commonly called the twin-plant. The final step consists in finding the possible sequences c :

M ≈0 c ≠ ae M from M
≈0 the initial marking of ≈ that lead to an ambiguous marking that can indefinitely occur.

Definition 13. A marking M in ≈ is ambiguous if: ÷p, p Õ oe P ≈ , M(p) ◊ M (p Õ ) " = 0 • ((¸(p) = F i • ¸(p Õ ) = N Õ i ) ' (¸(p) = N i • ¸(p Õ ) = F Õ i )
). Definition 14. A set of supervision patterns s is said to be involved in an ambiguous marking M , if:

F i oe ¸(M ) ≈∆ oe i oe s Definition 15. A sequence of transitions c oe T ú
≈ is ambiguous if it leads to an ambiguous marking. Definition 16. A set of supervision patterns s is said to be involved in sequence of transitions c oe T ú ≈ leading to a marking M , if s is involved in M .

We set Q

≈ = {q = q 1 fi q 2 : q 1 oe ¸≠1 « (F i ), q 2 oe ¸≠1 « Õ (N Õ i ), for i = 1..n}. Proposition 17. A reachable marking M of ≈ is ambiguous ≈∆ ÷c oe T ú ≈ : M ≈0 c ≠ ae M and ¸≈ (c) oe L(≈ ). Definition 18. A sequence of transitions c oe T ú ≈ is an admissible cycle in ≈ if ÷s oe T ú ≈ , ÷t oe T + ≈ : 'n oe N, ¸≈ (st n ) oe L(≈ ) • c = st.
From Definitions 15, 18 and Proposition 17 Proposition 19. c is an admissible cycle in ≈ =∆ c is an ambiguous cycle.

The diagnosability analysis (generalization of [START_REF] Gougam | Supervision patterns: Formal diagnosability checking by petri net unfolding[END_REF]) relies on the following result.

Theorem 20. « is not -diagnosable ≈∆ ≈ contains ambiguous cycles.

The notion of discriminability proposed in this paper can be analyzed based on the following: Theorem 21. A subset s oe 2 of supervision patterns is said to be discriminable ≈∆ s is not involved in any ambiguous cycle of ≈ .

So, the problem of patterns discriminability and diagnosability can be reduced to finding ambiguous cycles in ≈ .

To sum up, the method includes:

(1) modelling the supervision patterns and the system with labeled Petri nets;

(2) compute a meta-pattern and combine it with the system; (3) construction of a twin-plant; (4) unfolding the labeled Petri net of the twin-plant;

(5) search for ambiguous cycles in the twin-plant; (6) conclude on the discriminability of the patterns and consequently on the system diagnosability.

FINDING AMBIGUOUS CYCLES

To find cycles in a Petri net, we will use Petri net unfoldings. This technique -introduced by McMillan (1995) -attempts to avoid the combinatorial explosion inherent to the classical usage of marking graphs.

Petri net unfolding

A Petri net unfolding is another labeled Petri net that is generally infinite. [START_REF] Mcmillan | A technique of state space search based on unfolding[END_REF] shows the existence of a fragment of the unfolding Õ also called the finite complete prefix such that any reachable marking of « is represented by the cut of a configuration of that fragment. The construction of such a prefix relies on the search for cut-o points [START_REF] Mcmillan | A technique of state space search based on unfolding[END_REF], [START_REF] Esparza | An Improvement of McMillan's Unfolding Algorithm[END_REF]

). A cut-o point is a transition t c oe T Õ such that its local configuration [t c ] contains a transition t Õ such that ¸Õ(Cut([t Õ ])) = ¸Õ(Cut([t c ])) and the relation [t Õ ] ª [t]
holds, where ª is an adequate order (see [START_REF] Esparza | An Improvement of McMillan's Unfolding Algorithm[END_REF]). Let T c be the set of cut-o events which local configuration contains exactly one cut-o event. The finite complete prefix of Õ is then defined as t toeTc {[t] fi t•}. For every adequate order there is a di erent finite complete prefix of Õ appropriate to analyze a particular property of the Petri net. A partial order which leads to a complete finite prefix appropriate for detecting cycles is the strict set inclusion "µ".

Algorithm

Algorithm 1 looks for ambiguous cycles in the twin-plant ≈ . Algorithm 1 Search for ambiguous cycles 1: procedure analysis(≈ )

2: Õ Ω unfolding(≈ ) 3: H Ω cut-o s(Õ) 4:
for all e in H.events do end for 9: end procedure line 2: compute the unfolding of the Petri net ≈ . line 3: build a mapping between the cut-o events and their associated markings. This step can be performed while computing the unfolding by finding the maximal cuts -which represent reachable markings -including the postset of every cuto event. line 4-8: prune from H every non-ambiguous marking.

Once the algorithm is applied, we check H for possible remaining markings. If there is any, every supervision pattern involved in any marking is not discriminable and the system is not -diagnosable. Otherwise, the supervision patterns are discriminable and the system is -diagnosable.

The following section illustrates the method with the help of an example.

EXAMPLE

The method previously presented was implemented and in order to illustrate it, we present hereafter an example. The system is modeled by «, À uo = {e, f, g, k, h} represented in bold in Figure 2. There is two patterns oe 1 and oe 2 , the first models the parallel occurrence of two events {b, g}, the second models the sequential occurrence of k and h.

The table 1 summarizes the size of the Petri nets obtained at each step. We can see that even though the example is not strongly concurrent, the overhead in places and transitions is Finally, the remaining markings in H will have the following labels: {≠, N 1 , N 2 , F Õ 1 , N Õ 2 } and {≠, N Õ 1 , N Õ 2 , F 1 , N 2 }. This means that oe 1 is not discriminable, and consequently that oe 2 and the combination oe 1 &oe 2 are discriminable.

CONCLUSION AND PERSPECTIVES

In this paper, we introduced the notion of discriminability of supervision patterns and proposed a method to analyse it. The discriminability of a pattern ensures that one can detect the exclusive occurrence of this particular pattern, which di ers from its mere recognition without further information about other patterns. We have also shown that once the discriminability analysis is performed, we can conclude about the diagnosability of the system with no extra cost. Our approach relies on the construction of a meta-pattern embedding all interesting behaviors. After combining it with the system, we perform a twin-plant to detect ambiguous sequences by using petri net unfoldings.

An interesting continuation of this work could be the extension of the models to include timed systems and patterns. This would permit us to monitor more complex -and interesting -behaviors that can not be modeled otherwise.

  4) (stability) for each reachable marking M , ÷p oe P, M (p) > 0 and ¸(p) = F implies that for each successor marking M Õ : ÷p Õ oe P, M Õ (p Õ ) > 0 and ¸(p Õ ) = F .(5) (completeness) for each reachable marking M , 'e oe À, ÷t oe T : (¸(t) = e • 'p oe •t, M (p) > 0);

Figure 2 .

 2 Figure 2. Modeling of the system and the pattern reasonable. Plus, the completeness condition imposed on supervision pattern results in extra transitions that are striped away by the unfolding, whence the reduction of the number of transitions from ≈ to Õ.

  Where < is the transitive closure of the arc relation A # y) if there exist two transitions t 1 , t 2 oe T Õ , such that t 1 " = t 2 , •t 1 fi •t 2 " = ? and (t 1 , x), (t 2 , y) oe<.A configuration C of an unfolding is a set of causally-closed and conflict-free transitions of T Õ , formally:t oe C ∆ 't Õ < t, t Õ oe C and 't, t Õ oe C : ¬(t # t Õ ). The cut of a configuration C is the set of places Cut(C) = (M Õ0 fi C•) \ •C where C• = {p oe t•, t oe C} and •C = {p oe •t,t oe C} and ¸Õ(Cut(C)) characterizes a marking of the net «. The local configuration of a transition t oe T Õ is the set of transitions t Õ oe T Õ such that t Õ AE t. For any bounded Petri net,

	Õ , T Definition 22. The unfolding Õ = ÈP M Õ0 Í of a marked and labeled Petri net « = ÈP, T, A, Õ , A Õ , ¸Õ, P, T, ¸, L, À, M 0 Í, is a labeled Petri net such that: (1) 'p oe P Õ : |•p| AE 1. (2) Õ is acyclic, i.e. for any element x oe P Õ fiT Õ : ¬(x < x) (3) Õ is finitely preceded, i.e., for every x oe P Õ , the Õ fi T set of elements y oe P Õ such that y < x is finite. Õ fi T (4) No x oe P Õ fi T Õ is in self-conflict ¬(x # x). (5) ¸Õ(P Õ ) ™ P , ¸Õ(T Õ ) ™ T ; (6) 't oe T Õ : •¸Õ(t) is isomorphic to •t; Õ : ¸Õ(t)• is isomorphic to t•; (7) 't oe T (8) M
	Õ
	-called the causal relation, and AE the reflexive closure of <. The couple of elements (x, y) oe (P Õ ) 2 is a conflict Õ fi T (denoted x

Õ0 = {x oe P Õ : @y oe T Õ , y < x}.

Table 1 .

 1 Size of intermediary Petri nets of the method

	|P | |T |


Aurélie Névéol
email: aurelie.neveol@limsi.fr

Antonio Jimeno Yepes
email: antonio.jimeno@au1.ibm.com

L Neves

Karin Verspoor
email: karin.verspoor@unimelb.edu.au

Parallel Corpora for the Biomedical Domain

Keywords: Parallel corpus, biomedical domain, multilingual applications

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Parallel Corpora for the Biomedical Domain

Aurélie Névéol † , Antonio Jimeno Yepes * , Mariana Neves ‡ , Karin Verspoor

Introduction

Machine translation (MT) is currently being used for a variety of tasks and domains. It is known to play an important role in supporting readers' access to textual documents in a language other than their native language or for communicating in real time. The accuracy of MT systems has improved in recent years thanks to the availability of large collections of parallel and/or comparable corpora. In turn, these resources could be leveraged by deep learning methods, which created a paradigm shift for MT. MT plays an important role in the health domain. For instance, it has the potential to enable patients to read documents written in a language in which they are not fluent and to hold a conversation with foreign health professionals in case of accidents or health issues in a foreign country. Further, it allows patients to access health information which is only available in a foreign language, for instance, in the case of disease outbreak with origin in other countries (e.g., Zika virus outbreak in Brazil [START_REF] Bueno | Vigilância e resposta em saúde no plano regional: um estudo preliminar do caso da febre do Zika vírus[END_REF]). MT can also support researchers to access scientific literature only available in a foreign language, for instance, when working on tropical diseases specific of a region or even when moving to another country for research purposes [START_REF] Walker | Learn the local lingo to get ahead[END_REF]. Finally, MT can also support the biomedical natural language processing (BioNLP) domain when processing documents in languages other than English for which no specific NLP tools are available. This is often the case for clinical discharge reports that are usually only available in the local language. In such cases, researchers could translate the original document into English and rely on state-of-the-art BioNLP tools that are available for English (?). The biomedical and health domain is well known for its complex nomenclature, for which specific language resources and tools have been developed, e.g., lemmatiz-ers [START_REF] Liu | Biolemmatizer: a lemmatization tool for morphological processing of biomedical text[END_REF]. Therefore, specific training and test datasets are also necessary to precisely translate biomedical document across languages. However, despite its importance for the general population and researchers, there are very few parallel and comparable corpora specific for this domain.

In this paper, we present an overview of the stateof-the-art on parallel and comparable corpora for the biomedical domain. In a scoping review of existing resources, we characterize the resources available by language pairs and document type and provide pointers to more in-depth descriptions of the resources. Additionally, we present the parallel corpora that we assembled and built, such as EDP (French/English), ReBEC [START_REF] Neves | A parallel collection of clinical trials in portuguese and english[END_REF] (Portuguese/English) and Scielo [START_REF] Neves | The Scielo Corpus: a Parallel Corpus of Scientific Publications for Biomedicine[END_REF] (French/English, Portuguese/English and Spanish/English). For the latter, we provide details on the corpus construction, insights on the data and their utilization for the biomedical task [START_REF] Bojar | Findings of the 2016 Conference on Machine Translation[END_REF][START_REF] Jimeno Yepes | Findings of the WMT 2017 Biomedical Translation Shared Task[END_REF] of the Conference for Machine Translation (WMT). All corpora are available in our repository in GitHub1 .

Related Work

One of the first efforts that involved the development of large-scale shareable parallel corpora for the biomedical domain was the OPUS collection that contained medical documents from the European Medicines Agency (EMEA) [START_REF] Tiedemann | Parallel data, tools and interfaces in opus[END_REF] 2 . A number of biomedical parallel [START_REF] Widdows | Using parallel corpora to enrich multilingual lexical resources[END_REF][START_REF] Ozdowska | Traduction compositionnelle automatique de bitermes dans des corpus anglais/fran à §ais align à c s[END_REF][START_REF] Deleger | Translating medical terminologies through word alignment in parallel text corpora[END_REF] and comparable corpora [START_REF] Chiao | Aligning words in french-english non-parallel medical texts: effect of term frequency distributions[END_REF] have been used for terminology translation only. Similarly, the Mantra project [START_REF] Kors | A multilingual gold-standard corpus for biomedical concept recognition: the mantra gsc[END_REF][START_REF] Hellrich | Collaboratively annotating multilingual parallel corpora in the biomedical domain -some mantras[END_REF] provided corpora of biomedical articles automatically annotated for named-entity recognition for English, Spanish, French, German and Dutch. The corpora included MEDLINE titles, EMEA documents and patents in the biomedical field. While the goal of this project was to leverage annotation transfer from English to other languages to expand terminology coverage in languages other than English, to our knowledge, the corpus has not been used for machine translation. After general purpose machine translation systems were found to perform poorly on medical text [START_REF] Zeng-Treitler | Can multilingual machine translation help make medical record content more comprehensible to patients?[END_REF], the use of domain-specific data was investigated to improve MT system performance in the biomedical field. MEDLINE titles and terms from the Unified Medical Language System (UMLS) [START_REF] Lindberg | The unified medical language system[END_REF] were investigated first, due to easy availability [START_REF] Wu | Statistical machine translation for biomedical text: are we there yet?[END_REF][START_REF] Jimeno Yepes | Effect of additional in-domain parallel corpora in biomedical statistical machine translation[END_REF]. Abstract sentences were also found useful but difficult to obtain and share due to license issues (Jimeno Yepes et al., 2013). Recent work relied on a corpus of Cochrane Systematic Review Abstracts translated from English to French by professional translators at the French Cochrane Center. Preliminary work showed this dataset to be a good resource for domain-specific machine translation [START_REF] Neveol | Statistical machine translation of systematic reviews into French[END_REF]. Follow-up work further developed the corpus using postedited machine translation, which allowed the collection of a rich annotated parallel corpus [START_REF] Ive | Diagnosing high-quality statistical machine translation using traces of post-edition operations[END_REF] 3 . To encourage the community to take an interest in biomedical MT, recent challenges specifically provided targeted resources for system training and evaluation. The medical translation task at WMT 2014 [START_REF] Bojar | Findings of the 2014 workshop on statistical machine translation[END_REF] included some parallel biomedical collections: MuchMore, various patents, Wikipedia titles, Khesmoi search queries, and vocabulary lists extracted from the UMLS. The biomedical track at WMT 2016 [START_REF] Bojar | Findings of the 2016 Conference on Machine Translation[END_REF] provided new resources for French, Portuguese and Spanish with the Scielo corpus [START_REF] Neves | The Scielo Corpus: a Parallel Corpus of Scientific Publications for Biomedicine[END_REF]. The biomedical track at WMT 2017 [START_REF] Jimeno Yepes | Findings of the WMT 2017 Biomedical Translation Shared Task[END_REF] continued to offer new resources for French (EDP corpus), Portuguese and Spanish (extension of the Scielo corpus). The task also relied on the UFAL corpus, which comprises some of the previously released sources (EMEA, patents, ...) as well as newly crawled online patient information covering a total of ten language pairs. Previous work also reported comparable biomedical corpora collected from the Web for Spanish, Arabic and Japanese (Moreno-Sandoval and Campillos-Llanos, 2013). However, text seem to come from different sources and no study on the equivalence between the texts in the various languages seemed to have been carried out. Table 1 presents a list of biomedical parallel corpora used in the literature. We provide information regarding the text genre and language pairs covered by each source as well as pointers to a description of the resources. In the following sections, we describe more specifically the recent development of the EDP, ReBec and Scielo corpora.

3 http://www.translatecochrane.fr/corpus/

Method for Corpus Development

For all corpora we produced, we carried out the following procedure: (a) document retrieval or download; (b) document parsing and processing; (c) document (sentence) alignment; and (d) quality checking. Document retrieval and download. Document retrieval varies depending on the document collection, some are readily available for download while others need to be crawled from the corresponding Web site.

Document parsing and processing.

After download, the documents need to be parsed in order to extract the relevant text, e.g., title and abstract in the case of scientific publications. Documents in the different languages are then paired based on identifiers in the source websites. This step depends on the format of the obtained documents, whether XML or HTML format. Finally, we split the document into sentences using standard NLP tools.

Document (sentence) alignment.

The corpora described in this section do not result from organized professional translation. For this reason, the texts were not translated sentence by sentence as is often the case for professional translation of technical documents. Empirical inspection of the corpora suggests that while some of the documents reflect sentence by sentence translation, others were created more freely and the content in one language could be structured differently in the other language. We made the hypothesis that documents could nonetheless be aligned at the sentence level and we relied on automatic tools for performing the alignment. We identified alignment tools based on an evaluation of alignment for literary texts which is a genre that also features fuzzy alignment [START_REF] Xu | Sentence alignment for literary texts[END_REF].

Quality checking. After automatically aligning the sentences of the documents, we manually checked a sample of our corpora. This was carried out using the Appraise (Federmann, 2010) tool, and we evaluated whether the aligned sentences where correct or whether more information was available in one language or the other. Native speakers of each foreign language were responsible for this task.

Application to Three Biomedical Corpora

Here we describe the three corpora that we developed and highlight the differences regarding the particular tools that we used for the various steps above.

EDP

We identified five open access CC-BY journals, referenced EDP Sciences4 as having content in French and in English: the articles were originally written in French but the journals also publish the titles and abstracts in English, using a translation provided by the authors. Three journals are listed by the publisher under Health: "Actualités Odonto-Stomatologiques" and "Médecine Buccale Chirurgie Buccale", which are journals addressing dentistry and "Les Cahiers de Myologie", a journal addressing muscle medicine. Two journals are listed under Life & Environmental Sciences: "Cahiers Agriculture" and "Oilseeds and fats, Crops and Lipids". A list of the journal URLs was ob- tained5 and crawled6 on March 15, 2017. The html pages were parsed to extract the titles and abstracts in French and English as well as the author names. Any articles lacking some of this information were discarded.

The dataset was pre-processed for sentence segmentation using the Stanford CoreNLP toolkit7 for use in the WMT17 biomedical task. A manual reference for sentence segmentation was then created independently by revising baseline segmentation after the punctuation marks: full stop, interrogation point, exclamation point and colon.

Based on the manually validated sentence segmentation, the dataset was aligned automatically at the sentence level using YASA [START_REF] Lamraoui | Yet another fast, robust and open source sentence aligner[END_REF]. Manual evaluation conducted on a sample set suggests that 94% of the sentences are correctly aligned, with about 20% of the sentence pairs exhibiting additional content in one of the languages.

MEDLINE vernacular titles MEDLINE indexes journals in languages other than English that publish a title and abstract in English. In this case, MEDLINE citations include the title of the article in the vernacular language in addition to English. This has been used to develop parallel corpora to train machine translation methods [START_REF] Wu | Statistical machine translation for biomedical text: are we there yet?[END_REF]Jimeno Yepes et al., 2013).

We have retrieved the MEDLINE citations for articles in French, Spanish and Portugese available before the first WMT biomedical task8 . We collected titles in English and vernacular (Spanish, French and Portuguese). Titles are already aligned since they typically can be considered as one sentence. It can be noted that while our work was limited to the languages of interest in the WMT biomedical track, parallel titles and/or abstracts may also be retrieved for other languages. For instance, the query chinese [la] returns 286,151 results on September 29, 2017, and parsing the MEDLINE xml result file could yield several thousand aligned titles and abstract sentences for the relevant citations.

ReBEC As already described in [START_REF] Neves | A parallel collection of clinical trials in portuguese and english[END_REF], the construction of the ReBEC corpus followed the workflow described in the previous section. The Website site of the Brazilian Clinical Trials Registry 9 provides ways to easily download the trials in XML format, which was further parsed. However, given the various elements (sub-sections) in a trial, e.g., inclusion criteria, exclusion criteria, and given that some of these appear multiple times in the document, the automatic alignment of parallel documents is not straightforward.

Scielo Scielo (Scientific Electronic Library Online)10 is a database of open access scientific publications with a focus on developing and emerging countries, and especially on Latin America. All publications in Scielo are available under either the Creative Commons Attribution-Noncommercial 3.0 Unported (cc-by-nc) or Attribution 3.0 Unported (cc-by) licenses, which makes all documents suitable for redistribution and research purpose.

We developed a corpus based on Scielo (Scielo corpus [START_REF] Neves | The Scielo Corpus: a Parallel Corpus of Scientific Publications for Biomedicine[END_REF]) using the following procedure.

We crawled the Scielo site and retrieved articles periodically from Scielo. Our crawling has its starting point in the pages that list all journals from the "Biological Sciences" and "Health Sciences" subjects. These categories are used to compose the two datasets, with the corresponding names, of our corpus. Despite being distinct categories in Scielo, these are overlapping categories, as there are many journals that belong to both of them. From the list of journals, it is possible to retrieve a list of all issues of a particular journal, which is available in the regional web sites of Scielo in distinct countries, such as Brazil, Chile or Colombia. The HTML page of the journal's list of issues was further parsed to retrieve the page containing the list of articles of a given issue. Finally, we downloaded the page of a particular article and parsed the HTML code in order to extract the title and the abstract of each publication. Titles and abstracts were subsequently stored and indexed in the SAP HANA database. All translations of the abstracts in Scielo are the original texts provided by the authors of the publications, who are presumably not professional translators, and who may not have native proficiency in both languages. After the initial version of the corpus produced in 2016, we are using the same procedure to update the corpus on a yearly basis for the ENES and ENPT language pairs. For ENFR, there were no new documents added in 2017.

Results

Datasets Descriptive Statistics

Table 2 presents detailed statistics of the contents of the biomedical parallel corpora that we developped. Table 3 presents an overview of the corpora with the training and test set splits that were offered thoroughout the WMT campaigns.

Quality Assessment

We also provide a summary of the correct alignment rate for the various corpora, as shown in Table 4. The alignment was automatically carried out using the respective tools as previously described and a sample was manually checked using the Appraise tools for ReBEC and Scielo, and manual inspection of text files for EDP.

For EDP the manual reference for sentence segmentation provides an evaluation of Stanford sentence segmentation, which comes to 0.77 F-measure on the French portion and 0.81 F-measure on the English portion. Overall, error analysis reveals that the segmentation errors produced by the Stanford tool mainly result from segmentation of the section titles in structured abstracts (Introduction, Material and Method, Results...) which were considered as separate segments by the manual reference but not by the tools. Other errors occur due to organism names (e.g. E. coli, which may cause a sentence boundary to be set after "E.").

Data format

All corpora presented in the previous section are available from GitHub in the BioC format [START_REF] Comeau | Bioc: a minimalist approach to interoperability for biomedical text processing[END_REF], a standard XML format in the BioNLP community.

Discussion

In this section we present a short discussion on some interesting topics that raised during both the corpus construction and its use in our shared tasks.

6.1. Lessons learned during corpus construction.

The challenges of building parallel corpora for the biomedical include the identification of high quality relevant data that can be shared with the community. Technical issues then lie with the identification of adequate tools for sentence segmentation and alignment.

Sentence segmentation: we relied on tools which are non-specific for the biomedical domains, such as Stanford CoreNLP, OpenNLP and SAP HANA. However, we did observe issues. A specific discussion of sentence segmentation errors is reported in [START_REF] Neves | A parallel collection of clinical trials in portuguese and english[END_REF] for ReBEC. For the EDP corpus, we used intially used Stanford CoreNLP for sentence segmentation (in the version of the corpus distributed at WMT17). Then, we manually validated sentence segmentation in both languages in order to create a reference corpus that may be used to train and evaluate sentence segmentation tools. Therefore, Updated versions of the corpus reflect the manual sentence segmentation.

Sentence Alignment: GMA was used for Scielo and Re-BEC. Due to difficulties to install GMA, Yasa [START_REF] Lamraoui | Yet another fast, robust and open source sentence aligner[END_REF] was used for EDP; however, Yasa may be limited to the language pair en/fr. We can refer readers to [START_REF] Xu | Sentence alignment for literary texts[END_REF] for a discussion and evaluation of alignment tools for a specialized domain (literary texts). Nevertheless, both tools provided good automatic alignments (?). Additionally, GMA was used for two languages (es and pt) and two document types (scientific publications and clinical trials).

Differences across the corpora.

Despite the corpora presented in this work have been converted into a similar layout, we observed some differences across the results we obtained. These differences are mostly related to particularities of the corpora, such as its format.

One such example is the lower rate of correct alignments for the ReBEC corpus that was due to problems when parsing the document format rather that the alignment tool itself, though some few errors could have come from GMA. 6.3. Gaps to be addressed.

We can see from table 1 that there is no clinical corpus or datasets from the social media. Also, some languages benefit from better coverage than others depending on the corpora: DE, ES, FR, PT. Finally, we do not yet cover Asian languages, which we plan to address in the future through collaboration with members of the BioNLP community. Typically, we intend to create an abstract collection from MEDLINE as indicated in section 4.

Conclusion

We presented a scoping review of the various parallel corpora that are available for the biomedical domain. To our knowledge, this is the first survey of biomedical parallel corpora. In addition we detailed the development of corpora that we recently provided for training and evaluating biomedical machine translation systems. The collections cover a total of four languages (including English) and various types of documents, such as scientific publications and clinical trials, from various sources and databases. Further, these corpora have been evaluated on the scope of two shared tasks and are freely available for the scientific community either for MT or other NLP tasks. Finally, future work will contribute towards the inclusion of additional languages, e.g., German, as well as other documents types, e.g., health-related news and clinical reports.

Table 1 :

 1 ,de,el,es,eu, et,fi,fr,he,hu,hr (Lindberg et al., 1993) it,ja,ko,lt,lv,nl,no,pl,pt,sv,tr,zh Overview of biomedical parallel corpus. We use ISO 639-1 two-letter language codes. A star indicates resources that include previously developed corpora as well as new data

	Corpus	genre	languages (other than English)	reference
	Cochrane	Systematic Review (SR) abstracts	fr	(Ive et al., 2016)
	COPPA, PaTr	Patents	de,fr	(Bojar et al., 2014)
	EDP	Article titles and abstracts	fr	ibid.
	EMEA	Medication description	cs,da,de,el,es,et,fi,fr,hu,it
				lt,lv,mt,nl,pl,pt,ro,sk,sl,sv	(Tiedemann, 2012)
	Himl*	Patient information and SR abstracts	cs,de,fr	(Jimeno Yepes et al., 2017)
	Khresmoi	Short medical search queries	cs,de,fr	(Pecina et al., 2013)
	MEDLINE	Article titles	de,es,fr,hu,pl,tu	(Wu et al., 2011)
	MuchMore Springer	Article titles and abstracts	de	(Widdows et al., 2002)
	ReBEC	Clinical Trial summaries	pt	(Neves, 2017)
	Santé Canada	Patient information	fr	(Deleger et al., 2009)
	Scielo	Article titles and abstracts	es,fr,pt	(Neves et al., 2016)
	UFAL*	Medical web crawl	cs,de,es,fr,hu,pl,ro,sv	(Jimeno Yepes et al., 2017)
	UMLS	Metathesaurus cs,daCorpus Tokens Count method
		EDP
		EN	56,684 wc -w on txt files
		FR	62,333 wc -w on txt files
		ReBEC
		EN	625,881 reported by (Neves, 2017)
		PO	665,325 reported by (Neves, 2017)
		Scielo
		EN	20,337,385 script BioC2txtWithCounts.py
		ES	21,651,629 available on GitHub
		EN	525,866 reported by (Neves et al., 2016)
		FR	735,486 reported by (Neves et al., 2016)
		EN	18,769,613 script BioC2txtWithCounts.py
		PT	18,573,561 available on GitHub

Table 2 :

 2 Content of open biomedical parallel corpus.

Table 3 :

 3 Overview of the training and test sets. We present the number of documents and sentences in each corpus. Statistics for the MEDLINE dataset corresponds to both documents and sentences, given that it consists only of titles. For the Scielo test set collection, we present details of the WMT'16 (first row) and WMT'17 (second row) test sets.

	Corpus Rate of correct alignment
	EDP	94%
	ReBEC	67%
	Scielo	79%-85%

Table 4 :

 4 Summary of the rate of correct alignment for the corpora. No alignment was necessary for the MEDLINE titles.

http://github.com/biomedical-translation-corpora/corpora

http://opus.lingfil.uu.se/EMEA.php

http://www.edpsciences.org

Using http://www.xsitemap.com/

Using the perl utility wget

https://stanfordnlp.github.io/CoreNLP/

using the pubmed queries french [la], spanish[la] , portugese [la].

http://www.ensaiosclinicos.gov.br/

http://www.scielo.org

Acknowledgements

This work was supported in part by the Agence Nationale pour la Recherche (French National Research Agency) under grant number ANR-13-JCJC-SIMI2-CABeRneT. The authors would like to thank Arthur Boyer for his contribution to the EDP corpus.


Kevin Cohen

PhD Aurélie Névéol

PhD Jingbo Xia

MSc Negacy Hailu

PhD Lawrence Hunter

PhD Pierre Zweigenbaum

PhD K Bretonnel Cohen

Reproducibility in Biomedical Natural Language Processing

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

Introduction

There is a growing concern that the reproducibility of much work in science in general and in the biomedical field in particular is questionable. In order to improve the robustness of methods in biomedical Natural Language Processing (NLP), we need to assess the current situation in the field, after recent experiments on a shared task suggest reproducibility cannot be taken for granted even under favorable conditions where data, code and evaluation toolkits are available [START_REF] Névéol | Replicability of Research in Biomedical Natural Language Processing: a pilot evaluation for a coding task[END_REF] . Nonetheless, data and code availability is the first requirement to enable reproducibility.

Methods

Herein, we apply a protocol previously put forth to assess reproducibility in computer science 2 : all 29 articles in the proceedings of the 2016 BioNLP workshop are reviewed by two analysts (one expert in the field of biomedical NLP and one computer scientist) to extract information on code and data availability. The article passages supporting the evidence of availability are marked. However, the retrieval of the material and actual reproduction of experiments are not attempted at this stage, but would be impossible without data and code. The annotation guidelines are available at https://github.com/KevinBretonnelCohen/InterRaterAgreementReproducibility. They were created by writing an initial draft, doing a pilot annotation project, modifying the guidelines based on findings of the pilot project, and then doing the full annotation as described above. Inter analyst agreement is computed in terms of Cohen's kappa [START_REF] Cohen | Weighted kappa: Nominal scale agreement with provision for scaled disagreement or partial credit[END_REF] in order to assess the reliability of the annotation process as well as the understanding of the task by the analysts.

Results and Conclusion

Although 48% of papers provided pointers to data and 61% provided pointers to code, only 21% reported both. Inter-analyst agreement was 0.57 (moderate) for identifying data and 0.63 (substantial) for identifying code. This suggests that reports of data availability might require more domain knowledge to be identified, e.g. a link to github might be easier to follow as evidence of code availability than the name of a dataset possibly unknown to the reader In addition, some disagreement on data availability occurred for subsets of MEDLINE where the expert considered data as not available if the specific subset and annotations were not explicitly linked. Although the kappa scores that we are reporting for the inter-analyst agreement are not high, those numbers badly underestimate the reliability of the analysis, as the calculation sets the value for expected agreement too high, resulting in an inappropriately low kappa value. The situation with respect to reproducibility in clinical natural language processing is arguably better than the situation in computer science, as Collberg et al. found that only 13% of papers in their study reported both code and data availability 2 . However, we believe reproducibility in biomedical NLP should receive increased attention, with the introduction of guidelines for reporting work in a reproducible way. While the availability of code and data do not necessarily guarantee that work can be reproduced, it is a necessary condition and as a community we should strive to facilitate access to code, data and experimental set-up as a way to address reproducibility issues.

Acknowledgements

This project was funded in part by the EU H2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 676207 and by the National Natural Science Foundation of China (Grant No. 61202305).


J W Vásquez
email: jwvasque@laas.fr

L Travé-Massuyès

A Subias
email: subias@laas.fr

F Jimenez
email: fjimenez@uniandes.edu.co

C Agudelo
email: carlos.agudelo@ecopetrol.com.co

Alarm management based on diagnosis

Keywords: Alarm management, Diagnosis, Chronicles, Transitional stages, Hybrid models

The transitions between operational modes (startup/shutdown) in chemical processes generate alarm floods and cause critical alarm saturation. We propose in this paper an approach of alarm management based on a diagnosis process. This diagnosis step relies on situation recognition to provide to the operators relevant information on the failures inducing the alarms flows. The situation recognition is based on chronicle recognition where we propose to use the hybrid causal model of the system and the expertise to generate the pattern event sequences from which the chronicles will be extracted using the Heuristic Chronicle Discovery Algorithm Modified HCDAM . An illustrative example in the field of petrochemical plants is presented in the article.

INTRODUCTION

The petrochemical industries losses have been estimated at 20 billion dollars only in the U.S. each year, and the AEM (Abnormal Events Management) has been classified as a problem that needs to be solved. Hence the alarm management is one of the aspects of great interest in the safety planning for the different plants. In the process state transitions such as startup and shutdown stages, the alarm flood increases and generates critical conditions in which the operator does not respond efficiently. A dynamic alarm management is then required [START_REF] Beebe | The connection of peak alarm rates to plant incidents and what you can do to minimize[END_REF]). Currently, many fault detection and diagnosis techniques for multimode processes have been proposed; however, these techniques cannot indicate fundamental faults in the basic alarm system, [START_REF] Zhu | A dynamic alarm management strategy for chemical process transitions[END_REF]; in the other hand the technical report Advance Alarm System Requirements EPRI (The Electric Power Research Institute) suggests a cause-consequence and event-based processing. Therefore, in this paper, a dynamic alarm management strategy is proposed in order to deal with alarm floods happening during transitions of chemical processes. This approach relies on situations recognition (i.e. chronicle recognition). As, the efficiency of alarm management approaches depends on the operator expertise and process knowledge, our final objective is to develop a diagnosis approach as a decision tool for operators. The paper is divided into 5 sections. Section 2 presents the Chronicle based alarm management proposal. The Section 3 presents the case study related with an illustrative application in the petrochemical sector. Section 4 expresses the formal framework for this analysis including the hybrid causal model and the description of the chronicle discovery algorithm. Finally, the construction of the chronicle database is given in the section 5.

CHRONICLE BASED ALARM MANAGEMENT

The Chronicle Based Alarm Management (CBAM) methodology proposed in this paper merges different techniques to take the hybrid aspect and the standard operational procedures of the concerned processes into account. These two features stand out of the literature [START_REF] Jing | Fault diagnosis strategy for startup process based on standard operating procedures[END_REF], S. [START_REF] Xu | Hybrid model-based framework for alarm anticipation[END_REF], [START_REF] Srinivasan | A framework for managing transitions in chemical plants[END_REF], [START_REF] Bhagwat | Fault detection during process transitions: a model-based approach[END_REF]). Another important aspect is the analysis of the Dynamic Alarm Management: most of the time the alarm is assumed to be a static indicator, in our proposal an alarm is an event with an occurrence date and the alarm flow is formally modeled by a chronicle [START_REF] Vasquez | Chronicle based alarm management in startup and shutdown stages[END_REF]) as presented in section 4.2. Transposing this methodology to large-scale systems would benefit from a decentralized approach in which local chronicles would be learned and then integrated thanks to shared events. The main steps of this methodology are:

(1) From the standard operating procedures and from the evolution of the continuous variables, determine the set of event types in startup and shutdown stages. (2) From the expertise and the event abstractions determine the date of occurrence of each event type to construct the representative event sequences. In a general way, the chronicle learning requires a lot of representative event sequences of each scenario. In our case no historical information related to startup or shutdown stages is available, as these types of scenarios do not occur frequently. Therefore, it is by simulation that the representative event sequences of each scenario are obtained. The different steps of the methodology will be detailed further in the article and the next section presents the case study.

CASE STUDY -HTG (HYDROSTATIC TANK GAUGING) SYSTEM

The Cartagena Refinery in Colombia as recently be enriched by news units and elements. Our proposal aims at helping the operator to recognize dangerous conditions during the startup stage of the refinery with modified equipments. To start our analyze, we focus on the startup and shutdown stages in the unit of water injection. This process is a HTG (Hydrostatic Tank Gauging) system composed of passive components, active components and sensors. The passive components are components which cannot change the operational state, e.g. the tank (T K).

In the other hand, the active components can change their states of operation by a procedural action, e.g. the two normally closed valves (V 1 and V 2) and the pump (P u). The sensors, correspond to the instrumentation that measures the continuous variables, e.g. level sensor (LT ), pressure sensor (P T ), inflow sensor (F T 1 ) and outflow sensor (F T 2 ), see Fig. 1. The standard operating procedures give us the standard procedural actions for the startup and shutdown stages. For the correct execution of these procedures, the operators must execute the actions according to the correct evolution of the procedure. The abnormal situations are detected when the evolution of the procedural actions and the continuous variables evolution do not correspond to the standard operating procedure and wrong event type occurrences, happen. The fluctuations of the inlet flow of the tank, the response time of the pump that causes the outlet pressure and other conditions generate uncertain that can be determined by expertise. because to obtain a complex model which simulate all the process uncertain requires a lot of time and resources to build it.

FORMAL FRAMEWORK

This section presents the formal framework of the Chronicle Based Alarm Management (CBAM) methodology proposed.

Hybrid Causal Model

The hybrid system is represented by an extended transition system, whose discrete states represent the different modes of operation for which the continuous dynamics are characterized by a qualitative domain. Formally, a hybrid causal system is defined as a tuple [START_REF] Pons | Iterative hybrid causal model based diagnosis: Application to automotive embedded functions[END_REF]: Γ = (ϑ, D, T r, E, CSD, Init, COM P, DM C) (1) Where

• ϑ = {v i } is a set of continuous process variables which are function of time t. • D is a set of discrete variables. D = Q ∪ K ∪ V Q .
• Q is a set of states q i of the transition system which represent the system operation modes. • The set of auxiliary discrete variables K = {K i , i = 1, ...n c } represents the system configuration in each mode q i , where K i indicates the discrete state of the active components. • V Q is a set of qualitative variables whose values are obtained from the behavior of each continuous variable v i .

• E = Σ ∪ Σ c is a finite set of observable (Σ o ) and
unobservable (Σ uo ) event types, noted σ, where:

• Σ is the set of event type associated to the procedural actions in the startup or shutdown stages. • Σ c is the set of event type associated to the behavior of the continuous process variables. • T r : Q× Σ → Q is the transition function. The transition from mode q i to mode q j with associated event σ is noted (q i , σ, q j ).

• CSD ⊇ i CSD i is the Causal System Description
or the causal model used to represent the constraints underlying the continuous dynamics of the hybrid system.

Every CSD i associated to a mode q i , is given by a graph (G c = ϑ ∪ K, I). I is the set of influences where there is an edge e • Init is the initial condition of the hybrid system,

(v i , v j ) ∈ I from v i ∈ ϑ to v j ∈ ϑ if the variable v i influences variable v j . A dynamic continuous model DM C I K is associated to every influence I k ∈ I, see

Chronicle model

Let us consider time as a linearly ordered discrete set of instants. The occurrence of different events in time represents the system dynamics and a model can be determined to diagnose the correct evolution. An event is defined as a pair (e i , t i ), where e i ∈ E is an event type and t i is a variable of integer type called the event date. We define E as the set of all event types and a temporal sequence on E is an ordered set of events denoted S = (e i , t i ) j with j ∈ N l where l is the size of the temporal sequence S and N l is a finite set of linearly ordered time points of cardinal l. l=| S | is the size of the temporal sequence, i.e. The number of event type occurrences in S.

Definition 1: A chronicle is defined as a triplet C = (ξ, T , G) such that:

• ξ ⊆ E. ξ is called the typology of the chronicle.

• T is the set of temporal constraints of the chronicle.

• G = (V, A) is a directed graph where:

• V represent the event types of ξ • The arcs A represents the time constraints between event dates. [START_REF] Subias | Learning chronicles signing multiple scenario instances[END_REF])

If the event e 1 occurs t time units after e 2 , then it exists a directed link A from e 1 to e 2 associated with a time constraint. Considering the two events (e i , t i ) and (e j , t j ), we define the time interval as the pair

τ ij = [t -, t + ],
τ ij ∈ T corresponding to the lower and upper bounds on the temporal distance between the two event dates t i and t j .

The two next sections present what is an event in our approach and how are defined the events types we consider two sets of events; those generated by a qualitative abstraction fo the process continuous behaviour and those identified form the knowledge of standard operating procedures.

Event generation by qualitative abstraction of continuous behavior

In each mode of operation, variables evolve according to the corresponding dynamics. This evolution is represented with qualitative values. The domain

D(V i ) of a qualitative variable V i ∈ V Q is obtained through the function f qual : D(v i ) → D(V i
) that maps the continuous values of variable v i to ranges defined by limit values (High noted H i and Low noted L i ).

Fig. 3. Automaton G Vi f (v i ) qual =    V H i if v i ≥ H i V M i if L i < v i < H i V L i if v i ≤ L i (2)
The behavior of these qualitative variables is represented in Fig. 3 by the automaton

G Vi = (V Q , Σ c , γ) where V Q is the set of the possible qualitative states (V L i : Low, V M i : M edium, V H i : High) of the continuous variable v i , Σ c
is the finite set of events associated to the transitions and γ :

V Q × Σ c → V Q is the transition function.
The corresponding event generator is defined by the abstraction function

f V Q →σ f V Q →σ : V Q × γ(V Q , Σ c ) → Σ c ∀V i ∈ V Q , (V n i , V m i ) →        l + (v i ) if V L i → V M i l -(v i ) if V M i → V L i h + (v i ) if V M i → V H i h -(v i ) if V H i → V M i V n i , V m i ∈ {V L i , V M i , V H i } (3) Σ c = vi∈ϑ {l + (v i ), l -(v i ), h + (v i ), h -(v i )} (4)
4.4 Event identification from procedural action

In the system HT G of the case of study, the set of event types Σ that represent the procedure actions is:

Σ = {V 1 c,o , V 2 c,o , P u f -n , V 1 o,c , V 2 o,c , P u n-f , M/A}(5) where V 1 c,o (resp. V 2 c,o ) is for the action that switches the valve V 1 (resp. V 2) from closed to opened. V 1 o,c (V 2 o,c )
for the action that switches the valve V 1 (resp. V 2) from to opened to closed and P u f -n (reap. P u n-f ) for the action that turns on (reps. off) the pump. The event M/A corresponds to the transition from manual to automatic operation, closing the control loops. In the reminder we assume that this event is the only unobservable event of the system i.e. M/A ∈ Σ uo .

The underlying DES (Discrete event system) of the HTG system represents the sequence of observable procedure actions for a startup stage (indicated by the red or green arrows on Fig. 4) corresponding to the evolution of the operation modes (i.e q 0 , q 1 , q 4 , q 5 and q 7 ). To each operation mode q i is associated a causal system description to identify the influences between the variables L,P o and Q o (V 2) see Fig. 5. These influences allow to determine the event types Σ c occurrence. . CSD in the modes q 0 , q 1 , q 4 , q 5 , q 7

Σ c =      l + (L) , l - (L) , h + (L) , h - (L) , l + (P o) , l - (P o) , h + (P o) , h - (P o) , l + (Q oV 2 ) , l - (Q oV 2 ) , h + (Q oV 2 ) , h - (Q oV 2 ) (6)

Event sequence generation

The event sequences are generated according to the behavior of the system in each scenario. In the remainder, to simplify the notation, events types are labeled by letters such as a:

V 1 c,o , b: V 2 c,o , c: P u f -n , d: V 1 o,c , f : V 2 o,c , g: P u n-f , h: l + (L) , i: h + (L) , j: l - (L) , k: h - (L) , l: l + (P o) , m: h + (P o) , n: l - (P o) , o: h - (P o) , p: l + (Q oV 2 ) , q: h + (Q oV 2 ) , r: l - (Q oV 2 ) , s: h - (Q oV 2 ) .
Scenario 1, Normal startup According to the standard procedural actions, the first event type that must occur is a: V 1 c,o (Open V 1). After this event type occurrence, the system is in the mode of operation q 1 where the variable L increases and the event type h: l + (L) must occur between 1 and 4 time units after that the valve V 1 is opened, indicating that the level of the liquid into the tank T K has passed the limit of low level. Between 1 and 4 time units after h, the liquid into the tank must arrive to the high limit of the level and the event type i: h + (L) must occur. At this time point, the ordered sequence of event types that has occurred is a, h, i. The high limit of the level into the tank is the condition for continuing the procedure actions Open V 2 and T urn ON P u (b: V 2 c,o and c: P u f -n ). If the operator opens the valve V 2 first, the system passes in the mode of operation q 4 , but if the pump P u is turned ON first, the system passes in q 5 . The duration between the occurrences of event types b and c must be of 1 time unit, leaving the system in the mode of operation q 7 . At this time point, the ordered sequence of event types that has occurred must be a, h, i, b, c or a, h, i, c, b. In the scenario1 a : (a, h, i, c, b), the outlet pressure (P o) of the pump P u increases first of that the outlet flow (Q oV 2 ). Then, between 1 and 6 time units after of b, the pressure P o has passed its limit of low pressure and the event type l: l + (P o) must occur. The outlet flow after 1 unit time has passed its limit of low flow and the event type p: l + (Q oV 2 ) must occur. The high limit of pressure (m: h + (P o) ) occurs between 1 and 6 time units after p and the high limit of outlet flow occurs 1 time units after m. In the scenario1 b : (a, h, i, b, c), the event type p occurs between 3 and 4 time units and after c. At 1 time unit after p, l must occur. After l, the event type q must occurs between 3 and 4 time units and the event type m must occur 1 time unit after q. At this time point, the ordered sequence of event types that has occurred must be a, h, i, c, b, l, p, m, q or a, h, i, b, c, p, l, q, m. In this situation, the unobservable event type M/A occurs and the control loops are closed, carrying the system to a steady state. We assume that the control loops are closed whereas q occurs in the scenario1 a or m in the scenario1 b . Then, the event type k indicates that the level of liquid in the tank T K decreases from the high limit of level, between 1 and 4 time units after that the control loops are closed. In the same way, the outlet pressure and outlet flow decrease from its high limits (o and s) between 1 and 4 time units after that k occurs. The time units between s and o must be 1. When the event types o and s occur, we assume that the startup stage, finish correctly and the ordered sequences of event types must be a, h, i, c, b, l, p, m, q, k, o, s or a, h,i,b,c,p,l,q,m,k,s,o.

For this scenario, we chose the representative event sequences (Sp 1 , Sp 2 and Sp 3 ) that represent the extreme behaviors with all the possible sequence order of event types.

Sp 1 = (a, 6), (h, 7), (i, 8), (c, 9), (b, 10), (l, 11), (p, 12), (m, 13), (q, 14), (k, 15), (o, 16), (s, 17) Sp 2 = (a, 1), (h, 3), (i, 6), (b, 7), (c, 8), (p, 12), (l, 13), (q, 17), (m, 18), (k, 22), (s, 26), (o, 27) Sp 3 = (a, 1), (h, 5), (i, 7), (b, 8), (c, 9), (p, 12), (l, 13), (q, 16), (m, 17), (k, 21), (s, 24), (o, 25) The simulation of a normal startup is presented in Fig. 6 where we can see the evolution of the variables L in color blue, P o in color green and Q o (V 2) in color red. This simulation represents only one possible situation in this scenario related with the pattern sequence Sp 1 . Scenario 2, Abnormal startup This abnormal situation is related to a failure in the valve V 2. In this scenario the sequences of event types are the same that the event sequences of a normal startup, until that is detected that the outlet flow in the system does not increase. When the level of liquid in the tank T K arrived to its high limit, the ordered sequence of event types that has occurred must be a, h, i, c, b or a, h, i, b, c. In scenario2 a : (a, h, i, c, b) the event type l occurs after 1 time units of b. In scenario2 b : (a, h, i, b, c) the event type l occurs after 2 time units of c. The event type m occurs between 1 and 2 time units after l, then the ordered sequences of event types must be a, h, i, c, b, l, m or a, h, i, b, c, l, m. For this scenario, we chose the representative event sequences (Sp 4 , Sp 5 and Sp 6 ) that show the extreme behaviors with all the possible sequence order of event types.

Sp 4 = (a, 6), (h, 7), (i, 8), (c, 9), (b, 10), (l, 11), (m, 12) Sp 5 = (a, 1), (h, 3), (i, 6), (b, 7), (c, 8), (l, 10), (m, 12) Sp 6 = (a, 1), (h, 3), (i, 7), (b, 8), (c, 9), (l, 11), (m, 13) The simulation of this abnormal startup is presented in Fig. 7 where we can see the evolution of the variables L in the color blue and P o in color green. The variable Q o (V 2) (in red in Fig 6 ) does not appear because the valve V 2 failed. The limits P AL, P AH and P AHH correspond to the alarms of low, high and high high pressure. This simulation represents only one possible situation in this scenario related with the pattern sequence Sp 4 .

Heuristic Chronicle Discovery Algorithm Modified HCDAM

The chronicle exploration process corresponds in discovering all the chronicles, whose instances occur in a given temporal sequence of event types. In many cases the same situation does not implies temporal sequences perfectly identical. The HCDAM learns the chronicles, whose instances occur in all temporal sequences represented exhibiting the same situation [START_REF] Subias | Learning chronicles signing multiple scenario instances[END_REF]). Given a set of temporal sequences and a minimum frequency threshold, it finds all minimal frequent chronicles pre-sented in all temporal sequences. The chronicle learning algorithm has the following two phases:

(1) It builds a constraint database from a set of the temporal sequences (S) where it stores for each pair of event types its temporal constraints in a constraint graph structure. (2) It generates a set of candidate chronicles initializing with a set of chronicles that were proved to be frequent and it uses the constraint database to explore the chronicle space.

The base of the chronicles stores for each pair of event types its temporal constraints in a constraint graph structure. In this graph, time constraints are nodes of an acyclic graph whose arcs represent the relationship is parent of . Which is defined as: 2. Filtering on a given set of event types ε = {e i , e j , ..e k } if we are interested only those event types during processing. This option will be useful when we want to learn the patterns of a subset of event types.

CONSTRUCTION OF THE CHRONICLE DATABASE

An industrial or complex process P r is composed of different areas P r = {Ar 1 , Ar 2 , ...Ar n } where each area Ar k has different operational modes such as startup, shutdown, etc. The set of chronicles {C k ij } for each area Ar k is presented in the matrix below, where the rows represent the operating modes (i.e. O 1 : Startup, O 2 : Shutdown, etc) and the columns the normal and abnormal situations.

CAr k = O 1 O 2 . . . O j N f 1 f 2 . . . . . . f n     C k 01 C k 11 C k 21 . . . . . . C k i1 C k 02 C k 12 C k 22 . . . . . . C k i2 . . . . . . . . . . . . . . . . . . . . . . . . C k 0j C k 1j C k 2j . . . . . . C k ij     (7)
This chronicle database, is to be submitted to a chronicle recognition system that identifies in an observable flow of events all the possible matching with the set of chronicles from which the situation (normal or faulty) can be

Using HCDAM

We present two chronicles (C 1 01 and C 1 11 ) of the set of chronicles of the HTG (Hydrostatic Tank Gauging) system i.e of the area Ar 1 of the whole system. C 1 01 is a chronicle describing the normal start up stage of the HT G and C 1 11 is associated to failure behavior of type f 1 during a startup stage.

Scenario 1, Normal startup:

The chronicle C 1 01 that resulted using the algorithm HCDAM is presented in Fig. 8. The pattern event sequences used are the Sp 1 , Sp 2 and Sp 3 generated in section IV.

Scenario 2, Abnormal startup: The chronicle C 1 11 that resulted using the algorithm HCDAM is presented in Fig. 9. The representative event sequences used are the Sp 4 , Sp 5 and Sp 6 generated in section IV. Similar to the language theory, in the chronicles the alphabet corresponds to E. The timed language L T (ξ, T ) of each chronicle C will be referenced in the strings w that can be generated according to the typology of the chronicle and the concatenation of the elements in the strings will be restricted by the set of temporal constraints T .

CONCLUSION

A preliminary method for alarm management based on a diagnosis process has been proposed. The proposal is based on a hybrid causal model of the system and a chronicle based approach for diagnosis. An illustrative example of an hydrostatic tank gauging has been considered to introduce the main concepts of the approach. The algorithm HCDAM is a tool for the automatic generation of the chronicles from representative event sequences. Transposing this methodology to large-scale systems would benefit from a decentralized approach in which local chronicles Fig. 9. Chronicle C 1 11 resulted using the HCDAM in the abnormal startup scenario would be learned and then integrated thanks to shared events.

Fig. 1 .

 1 Fig. 1. Hydrostatic Tank Gauging (3) From the representative event sequences in each scenario, determine the chronicle database using the algorithm HCDAM (Heuristic Chronicle Discovery Algorithm Modified).

Fig. 2 .

 2 The model of the active component corresponds to a transfer function of first order with delay. The set of components is noted as COM P .

Fig. 2 .

 2 Fig. 2. Dynamic Model of Control DM C

Fig. 4 .

 4 Fig. 4. Underlying DES of the HTG system

Fig. 6 .

 6 Fig. 6. Simulation of a normal startup

Definition 3 :

 3 The graph of constraints is defined as the tuple GC = (ε, τ, G c ) containing time constraints, which are nodes in an oriented acyclic graph whose arcs represent the inclusion relations of the constraints. ε ⊆ E with ∀e i ∈ E, e i ≤ E e i+1 : A finite set of event types is called the typology of the constraint graph. T = {τ 1 , τ 2 , ..., τ p } is the set of time constraints of the chronicle. G c = (T , A c ) is a directed graph whose nodes represent the time constraints valid for a given frequency and the arcs A c represent the relationships is parent of . As this analysis is for several sequences, only the pairs of event types which are present in all sequences, are processed. This leads us to the first stage of the constraint graph construction that it is the f iltering operation. Definition 4: The f iltering operation is a preliminary treatment on sequences and it can be summarized in two possible actions: 1. Filtering the event types not present in all sequences S. If ∃S k ∈ S such as ∃e i ∈ S k , then e i will be removed of all other sequences.

Fig. 8 .

 8 Fig. 8. Chronicle C 1 01 resulted using the HCDAM in the normal startup scenario assessed. In the following subsection are presented two chronicles (C 1 01 and C 1 11 ) of the set of chronicles of the HTG (Hydrostatic Tank Gauging) system i.e of the area Ar 1 of the whole system. C 1 01 is a chronicle describing the normal star up stage of the HT G and C 1 11 is associated to failure behavior of type f 1 during a startup stage.

  Definition 2: The node e i [t -, t + ]e j is parent of another e i [t -, t + ]e j if, only if [t -, t + ] ⊂ [t -, t + ] and not exist e i [t -, t + ]e j such that [t -, t + ] ⊂ [t -, t + ] ⊂ [t -, t + ]

ACKNOWLEDGEMENTS

The ECOPETROL -ICP engineers Jorge Prada, Francisco Cala and Gladys Valderrama help us to develop and validate the simulations.