Mathilde Boltenhagen
email: boltenhagen@lsv.fr

Thomas Chatain
email: chatain@lsv.fr

Josep Carmona
email: jcarmona@cs.upc.edu

A Discounted Cost Function for Fast Alignments of Business Processes

Alignments are a central notion in conformance checking. They establish the best possible connection between an observed trace and a process model, exhibiting the closest model run to the trace. Computing these alignments for huge amounts of traces, coming from big logs, is a computational bottleneck. We show that, for a slightly modified version of the distance function between traces and model runs, we significantly improve the execution time of an A*based search algorithm. We show experimentally that the alignments found with our modified distance approximate very nicely the optimal alignments for the classical distance.

Introduction

Conformance checking techniques enable establishing a relation between modeled and observed behavior [START_REF] Carmona | Conformance Checking -Relating Processes and Models[END_REF]. The techniques on this field are grounded on solving a very particular problem, known as alignment [START_REF] Adriansyah | Aligning observed and modeled behavior[END_REF]: given a process model that describes a certain process, and a trace which contains a potential observation of this process, to decide if the trace is in the language of the model, and if not, to pinpoint where it deviates. Computing alignments is not necessarily the ultimate goal of an analysis, but instead can be used to further enhance a process model with the evidences found in the data, e.g. depicting in the model explicitly the bottlenecks of the underlying process [START_REF] Wil | Process Mining -Data Science in Action[END_REF].

As happened a decade ago with process discovery, process mining software vendors are seriously considering incorporating conformance checking capabilities in their solutions, since conformance checking unleashes the full potential of model-based reasoning on top of real process data. However, whilst process discovery techniques may rely on light techniques, based on the directly-follows relations computed in event log [START_REF] Sander | Discovering block-structured process models from event logs containing infrequent behaviour[END_REF][START_REF] Augusto | Split miner: automated discovery of accurate and simple business process models from event logs[END_REF] without significantly sacrificing the quality of the obtained solution, conformance checking techniques instead need to fight the state-space explosion problem, due to the need to explore, when computing alignments, the behavior underlying the process model. Hence, industry adoption for conformance checking is still not widespread.

The current process mining field is living an interesting paradox: whilst it is widely accepted that the capabilities of discovering huge process models exist, when it comes to analysing these discovered models through conformance checking techniques, only approximate techniques for deriving alignments are used in practice. In the next section we provide a complete overview of current alternatives for alignment computation.

In this paper, however, we somehow go back to the roots, and adopt the seminal work from Arya Adriansyah's PhD thesis [START_REF] Adriansyah | Aligning observed and modeled behavior[END_REF] as main alignment algorithm. In the aforementioned work, an A * graph search algorithm is proposed over the graph corresponding to the state space of synchronous product net. This net is made out of the initial process model and a trace net corresponding to the input trace. The cost function that governs the A * search is typically a standard cost function which assigns unitary costs to all the possible types of deviations.

We consider a rather simple, yet powerful idea that is motivated from the following use case: for certain processes, the costs associated to deviations at early stages of the process' execution are more important than the ones at the end. For instance, consider a loan application process that has two decisions: one at the beginning, assessing the type of customer (gold, silver, normal), and one at the end, determining whereas the loan was received in a labour day or not. It is normal that the stage in which these decisions are made in any possible execution of the process reveal their importance. For instance, if for the company it is very important to know the type of the customer so that other further information needs to be gathered depending on the customer's type, then it is likely that the corresponding process has the type of customer decision close to the start of any possible execution. On the contrary, if the day when the loan was received is not so important, then it is likely that the corresponding events will be pushed to the end of the traces.

Having this in mind, one can instantiate the A * algorithm to make the cost function exponentially biased to this use case: giving more importance (higher cost) to the deviations that occur in early stages of the alignments, and exponentially reducing the cost as the search algorithm progresses. Importantly, this discounted cost function has a huge impact on the size of the search space required for the A * search, since the cost asymmetry makes the search space to rapidly shrink after the first alignment steps are made.

For processes which follow the aforementioned use case, this cost function puts the search focus in the right place, deriving alignments that aim at synchronizing modeled and observed behavior in the important decisions that are made at the beginning. Interestingly, this idea can also be used for processes that are not following this trend, since although putting the focus at the beginning may not be the most likely explanation, the computational alleviation can make the problem tractable, where other techniques fail.

In this paper we formalize this simple idea, and show the great impact in performance with respect to several variations of the A * search proposed in the last years. Surprisingly, this improvement is with a very minor loss in quality: as we will see in the experiments, for well-known and accepted benchmarks, the proposed techniques is often able to produce alignments very close to the optimal ones. This paper is organized as follows: in the next section we provide a detailed overview of the different techniques to compute alignments. Then in Section 3 we provide the necessary definitions to understand the technique of this paper. In Sections 4 and 5 we provide the formal definition and corresponding algorithmic adaptations for the discounted cost function presented in this paper. Then in Section 6 an evaluation of the proposed technique is reported, and Section 7 concludes the paper.

Related Work

The seminal work in [START_REF] Adriansyah | Aligning observed and modeled behavior[END_REF] proposed the notion of alignment and developed a technique based on A * to compute optimal alignments for a particular class of process models. The approach represents the state-of-the-art technique for computing alignments, and can be adapted (at the expense of increasing significantly the memory footprint) to provide all optimal alignments. Alternatives to A * have appeared in recent years: in the approach presented in [START_REF] De | Aligning real process executions and prescriptive process models through automated planning[END_REF], the alignment problem is mapped as an automated planning instance. Automata-based techniques have also appeared [START_REF] Reißner | Scalable conformance checking of business processes[END_REF][START_REF] Sander | Scalable process discovery and conformance checking[END_REF]. The techniques in [START_REF] Reißner | Scalable conformance checking of business processes[END_REF] (recently extended in [START_REF] Reißner | Scalable alignment of process models and event logs: An approach based on automata and s-components[END_REF]) rely on state-space exploration and determination of the automata corresponding to both the event log and the process model, whilst the technique in [START_REF] Sander | Scalable process discovery and conformance checking[END_REF] is based on computing several subsets of activities and projecting the alignment instances accordingly.

The work in [START_REF] Taymouri | A recursive paradigm for aligning observed behavior of large structured process models[END_REF] presented the notion of approximate alignment to alleviate the computational demands by proposing a recursive paradigm on the basis of the structural theory of Petri nets. In spite of resource efficiency, the solution is not guaranteed to be executable. Alternatively, the technique in [START_REF] Taymouri | Model and event log reductions to boost the computation of alignments[END_REF] presents a framework to reduce a process model and the event log accordingly, with the goal of alleviating the computation of alignments. The obtained alignment, called macro-alignment since some of the positions are high-level elements, is expanded based on the information gathered during the initial reduction. Techniques using local search have recently been also proposed very recently [START_REF] Taymouri | Computing alignments of well-formed process models using local search[END_REF].

Decompositional techniques have been presented [START_REF] Wil | Decomposing Petri nets for process mining: A generic approach[END_REF][START_REF] Munoz-Gama | Single-entry single-exit decomposed conformance checking[END_REF][START_REF] Verbeek | Merging alignments for decomposed replay[END_REF] that, instead of computing optimal alignments, they focus on the crucial problem of whether a given trace fits or not a process model. These techniques vertically decompose the process model into pieces satisfying certain conditions (so only valid decompositions [START_REF] Wil | Decomposing Petri nets for process mining: A generic approach[END_REF], which satisfy restrictive conditions on the labels and connections forming a decomposition, guarantee the derivation of a real alignment). Later on, the notion of recomposition has been proposed on top of decompositional techniques, in order to obtain optimal alignments whenever possible by iterating the decompositional methods when the required conditions do not hold [START_REF] Lam | Recomposing conformance: Closing the circle on decomposed alignment-based conformance checking in process mining[END_REF]. In contrast to the aforementioned vertical decomposition techniques, our methodology does not require this last consolidation step of partial solutions, and therefore can be a fast alternative to these methods at the expense of loosing the guarantee of optimality.

We believe our work has similarities and synergies with two recent works. In [START_REF] Vincent Bloemen | Maximizing synchronization for aligning observed and modelled behaviour[END_REF], a symbolic algorithm to maximize the number of synchronous moves in the alignment is proposed. Recently, in [START_REF] Sebastiaan | Online conformance checking: relating event streams to process models using prefix-alignments[END_REF], an online alignment technique with a window-based backwards exploration is proposed. In both cases, the technique of this paper can be used to enhance the aforementioned techniques.

Preliminaries

We represent event data as log traces and process models as labeled Petri nets.

Definition 1 (Log Traces). Let Σ be a set of activities. We define a log L as a finite multiset of sequences σ ∈ Σ * , which we refer to as log traces. Definition 2 (Process Model (Labeled Petri Net) [START_REF] Murata | Petri nets: Properties, analysis and applications[END_REF]). A Process Model defined by a labeled Petri net system (or simply Petri net) is a tuple N = P, T, F, m 0 , m f , Σ, λ , where P is the set of places, T is the set of transitions (with P ∩ T = ∅), F ⊆ (P × T ) ∪ (T × P ) is the flow relation, m 0 is the initial marking, m f is the final marking, Σ is an alphabet of actions and λ : T → Σ ∪ {τ } labels every transition by an activity or as silent.

Semantics. The semantics of Petri nets is given in term of firing sequences. Given a node x ∈ P ∪ T , we define its pre-set

• x def = {y ∈ P ∪ T | (y, x) ∈ F } and its post-set x • def = {y ∈ P ∪ T | (x, y) ∈ F }.
A marking is an assignment of a non-negative integer to each place. A transition t is enabled in a marking m when all places in • t are marked. When a transition t is enabled, it can fire by removing a token from each place in • t and putting a token to each place in t

• . A marking m is reachable from m if there is a sequence of firings t 1 . . . t n that transforms m into m , denoted by m[t 1 . . . t n m . The set of reachable markings from m 0 is denoted by [m 0 . A Petri net is k-bounded if no marking in [m 0 assigns more than k tokens to any place. A Petri net is safe if it is 1-bounded. A full run of a Petri net N is a firing sequence m 0 [t 1 . . . t n m f
from the initial marking m 0 to the final marking m f . A Petri net is easy sound [START_REF] Adriansyah | Memory-efficient alignment of observed and modeled behavior[END_REF] if it has at least one full run, i.e. m f is reachable from m 0 .

In this paper we assume safe and easy sound Petri nets.

Definition 3 (Alignments). Given a log trace σ = σ 1 , . . . , σ m ∈ L of alphabet Σ, and a process model N = P, T, F, m 0 , m f , Σ, λ , an alignment of σ with N is a finite sequence ϕ = (σ 1 , u 1 ), . . . , (σ p , u p ) of moves such that:

each move is either: a synchronous move (a, t) ∈ Σ × T with a = λ(t), a log move (a, ) (where is a special 'skip' symbol), or a model move ( , t),

dropping the symbols from the left projection σ 1 , . . . , σ p of ϕ, yields σ; dropping the symbols from the right projection u 1 , . . . , u p of ϕ, yields a full run u of N . 1a) and a log trace (Fig. 1b). An alignment of N and σ is ϕ = ( , a), (b, b), (c, c) .

In order to compare the quality of alignment quality, we define a cost function which penalizes log moves and model moves.

Definition 4 (Classical Alignment Cost Function, Optimal Alignments). For every alignment ϕ between a model N and a log trace σ, the Classical Alignment Cost Function C assigns a cost 0 to synchronous moves and a cost 1 to log moves or model moves. The cost of an alignment is the sum of the costs of its moves. An alignment between a model N and a log trace σ is optimal if it minimizes the cost. The optimal alignment cost given with the classical alignment cost function C gives the Levenshtein edit distance between a run of M and the trace σ.

Definition 5 (Levenshtein Edit distance). The Levenshtein Edit Distance dist(u, v) between two words u and v ∈ Σ * is the minimal number of edits needed to transform u to v. In our case, edits can be deletions or insertions of a letter in words.

The main methods of the literature to compute optimal alignments are Dijkstrabased algorithms which often implies the construction of the Synchronous Product between the given process model and a sequential Petri net representing the log trace [START_REF] Adriansyah | Aligning observed and modeled behavior[END_REF].

Definition 6 (Synchronous Product for Alignments). For a log trace σ = σ 1 , . . . , σ m defined in Σ\ and a process model N = P, T, F, m 0 , m f , Σ, λ , the Synchronous Product SN = P SN , T SN , F SN , m SN0 , m SN f , Σ, λ SN of alignments between N and σ is given by a product of Petri nets such as:

-N σ = P σ , T σ , F σ , m σ0 , m σf , Σ, λ σ is a translation of σ to a sequential Petri net with: The Dijkstra-based algorithm for finding optimal alignments, explores the reachability graph of the synchronous product of Def. 6. Weights are given by the transitions fired to reach the markings, according to the type of move that they represent. The best firing sequences found for reaching a marking is the less costly one. The algorithm that we present in Section 5 is an adaptation of this classical Dijkstra-based algorithm for alignments. As we are using easy-sound Petri nets as process models, the Synchronous Products for Alignments are easy-sound which implies termination of the Dijkstra algorithm with the condition to reach the final marking m SN f [START_REF] Winskel | Petri nets, algebras, morphisms, and compositionality[END_REF].

P σ = {P σ0 , . . . P σm }, T σ = {t σi = λ σ (σ i ) | i ∈ {1, . . . , m}}, F σ = {(P σi-1 , t σi ), (t σi , P σi ) | i ∈ {1, . . . , m}}, m σ0 = {P σ0 : 1}, m σf = {P σm : 1}, -P SN = P ∪ P σ -T SN = T ∪T σ ∪T S , where T = {( , t) | t ∈ T } represents the model moves, T σ = {(t, ) | t ∈ T σ } represents the log moves, T S = {(t 1 , t 2 ) | t 1 ∈ T, t 2 ∈ T σ and λ(t 1 ) = λ σ (t 2 )} represents the synchronous moves, -F SN = F ∪F σ ∪{(P i , t i ) | t i = (t 1 , t 2 ) ∈ T SN , t 1 = , t 2 = , P i ∈ • t1∩ • t2} ∪ {(t i , P i ) | t i = (t 1 , t 2 ) ∈ T SN , t 1 = , t 2 = , P i ∈ t 1 • ∩ t 2 • } -m SN0 = m 0 ∪ m σ0 , -m SN f = m f ∪ m σ f , -λ SN maps every t ∈ T SN to its move. Example 3.

Discounted Cost Function and Properties

The classical alignment cost function corresponds to Levenshtein edit distance between a run of a process model and a log trace, where additions and deletions represent model and log moves. In this section, we introduce the Discounted Edit Distance and its impact when using it as alignment cost function.

The idea of this Discounted Edit Distance is to penalize more insertions and deletions when they occur at the beginning of the strings, and less when they occur later.

Definition 7 (Discounted Edit Distance). We define the Discounted Edit Distance between two strings u and v (of length |u| and |v| respectively) with discount parameter E ≥ 1 by D u,v E (|u|, |v|, 0) where:

D u,v E (i, j, k) =                    0 if (i = 0 and j = 0) D u,v E (i -1, j -1, k + 1) if (u i = v j ) D u,v E (i, j -1, k + 1) + E -k if i = 0 D u,v E (i -1, j, k + 1) + E -k if j = 0 min D u,v E (i -1, j, k + 1) + E -k D u,v E (i, j -1, k + 1) + E -k otherwise.
thus allowing equation ((u i = v j )) for free and insertions and deletions at cost

E -k
where k refers to the position where the edit occurs.

Lemma 1. For E = 1, the Discounted Edit Distance corresponds to the Levenshtein distance.

In practice, relevant values for the discount parameter E are slightly larger than 1. For E = 2, the discount is already very severe since an edit at position k costs more than the sum of all the following edits.

Lemma 2. With the Discounted Edit Distance, for E = 2, an edit at position k costs more than the sum of all the following edits.

Proof. For u and v, two words, let k be the position of a non-free cost in D u,v E . We note its cost c(k) and for

E = 2, c(k) = 2 -k .
The next edits can occur at positions j ∈ {k + 1, . . . , n} where, in the worst case, n = |u|+|v|. We write S(j, n) the sum of costs. The maximal value of this sum appears when only non-free edits are used by the discounted edit distance:

S(k, n) = n j=k+1 c(j) = 2 -(k+1) + 2 -(k+2) + • • • + 2 -n = 2 -k -2 -n Hence, c(k) = 2 -k > S(k, n).
Otherwise, in the best case, there is no edit after position k and the cost of the edit at position k is higher than a null sum. Similarly to the Levenshtein edit distance, the Discounted Edit Distance can be applied to alignments. Definition 8 (Discounted Cost Function for Alignments). For an alignment ϕ = (σ 1 , u 1 ), . . . , (σ p , u p ) between a process model N and a log trace σ, the Discounted Cost Function for Alignments assigns a cost 0 to every synchronous move and E -k to every pair (σ k , u k ) that is either a log move either a model move, where k ∈ {1, . . . , p}, p ∈ N is the length of the alignment, and E ≥ 1 is the discount parameter.

For E = 1, the Discounted Cost Function for Alignment is equivalent to the Classical Alignment Cost Function. However when E > 1, the costs of moves are dynamic and depend on the number of previous moves of the alignment. (c,c) , presented in the first example, the cost of ( , a) is E -1 because it is the first move of the alignment. For ϕ = (b, b), ( , d), ( , e), ( , τ ) which is certainly not an optimal alignment but still an alignment of σ = b, c and the Petri net N of Fig. 1a, the cost of ( , e) is E -3 . Lemma 3. For E > 1, a non-free move ω of position j, any move of position k > j costs less than ω.

As a consequence, algorithms for computing optimal discounted alignments will tend to align in priority the prefixes of the log traces. Suffixes are less costly. From Lemma 2, when the discount parameter is E = 2, a non-free move of position j is more costly than the sum of all the next costs.

Using the Discounted Cost Function in an A*-based Algorithm for Discounted Alignments

To compute alignments by using the discounted cost function, we present an A*-based algorithm which assigns weights to the explored states according to the discounted cost function for alignment. Let E be the discount parameter. Then, to a state reached by a move ω occurring in position i, will be assigned the weight of its predecessor, increased by the cost

h(ω, i, E) def = (0 if ω is a synchronous move, E -i otherwise).
As a result of Lemma 3, this heuristic aims at aligning prefix first more than suffixes.

The function h, based on the discounted cost function, is easily incorporated in the state-of-the-art algorithms for computing alignments. We present two versions of the incorporation, one by using the synchronous product of the process model and the log trace, and another one that avoids the computation of the product by exploring the process model along with the trace.

Algorithm for Computing Optimal Discounted Alignments

Our algorithm Alg. 1, noted A * SP D=E , is adapted from [START_REF] Carmona | Conformance Checking -Relating Processes and Models[END_REF]. It proceeds by exploring the state space of the synchronous product of the process model with a sequential Petri net representing the log trace as defined in Def. 6. An optimal alignment corresponds to the shortest path between the initial marking to the final marking of the synchronous product. For the discounted cost function, a state contains a marking and the length of the current sequence to reach the marking. For instance line 2 contains m 0 , 0 which corresponds to the initial state.

Each state is associated to a cost which is stored in the function d. Cost of states are given by the optimal firing sequences of transitions to reach the states. Some transitions of the synchronous product correspond to the log and model moves and are costly. The other transitions are the synchronous moves and are free. In Fig . 1c, the green transition are free and all the other aren't.

Our discounted cost function h appears on line 19. It determines if the move is costly and attributes the cost given the current length of the alignment, i.e, the position of the move j, and the parameter E.

The algorithm returns the best sequences of moves to reach the final marking.

Role of Length in States

In the classical version of alignment computation, the state contains the markings only. However, the length of the current alignment plays an important role in the discounted cost function. Indeed, the first visit of a marking might not be the optimal one, as it is the case in the classical version of alignments. A same marking ω can be reached with different firing sequences of moves of different lengths.

The first path that gives the first visit of the marking ω is the shortest one. Let's call this short path γ short , and γ long a longer path from the initial marking to this marking ω. We have |γ long | > |γ short |. However, γ short might contain future costly moves to reach the final marking. If those moves are of position lower than |γ long |, it questions the optimality of γ short . We give an example of this situation below.

Example 7. Let's suppose that silent transition labelled by τ costs for this example. To reach marking ω = {p4 : 1, p α2 : 1}, the algorithm can play γ = ( , a), ( , b), ( , tau), (b, b) whose cost is E -1 + E -2 + E -3 . This firing sequence costs as much as γ = ( , a), ( , b), (b, ) which reaches the same marking ω. However we notice that γ has a synchronisation at position 4 but we don't know yet what appear at position 4 for γ . Then both paths should be kept.

Notify that we tackled the problem of optimality of the alignment with the discounted cost function. For E > 1, this optimality does not correspond to the optimal classical alignment. Input : SP = ((P, T, F, λ, m 0 , m f )): synchronous product,

E: discount parameter 1 A ← ∅ Initialise closed set 2 X ← { m 0 , 0 } Initialise open set 3 p( m 0 , 0 ) = null Initialise predecessor function 4 ∀ m∈RS(SN ) ∀ i∈{0,...,max |u|,u∈Runs(SP ) } d( m, i ) = ∞ Initialise function d 5 d( m 0 , 0 ) = 0 6 while X = ∅ While not all states visited 7 do 8 m, i ← m, i ∈ X minimizing d(m)
Get the closest state Comparison to Classical Alignments Due to the discount parameter E in the discounted cost function, our heuristic prioritizes the alignment of the beginning of the log trace. In the algorithm, this difference with the classical alignment algorithm appears line 9 of Alg. 1 where the markings that minimize the cost are much more different with the discounted cost function than by using the classical cost function for alignments. Indeed, when costs are all equivalent, many paths compete in the search for the optimal alignment. However, with very different costs, the number of paths with similar costs is low, thus reducing the search space. This characteristic is well observed in practice with a reduction of runtime.

9 if m = m f then 10 break while 11 A ← A ∪ { m, i
Example 8. For the example of Fig. 1, there is a first choice between a and b. For large E, the decision is quickly given thus disabling testing the depth of the other paths. For instance, with E = 2, the log sequences of type a, b, c , a, b, τ, b, c , a, b, τ, b, τ, b, c won't be explore because they cannot have a better discounted cost. Then the search space is very reduced.

A Heuristic for Reducing the Search Space of the Algorithm

The search space of A * SP D=E is large and even larger than the Dijsktra-based algorithm for alignments due to the incorporation of the lengths in the states. To reduce it, we come back to the classical states that contain the markings only. Every m, i of Alg. 1 is reduced to m (like in [START_REF] Carmona | Conformance Checking -Relating Processes and Models[END_REF]). With this reduction, only the first path that reaches the marking is used. When several concurrent firing sequences of equal cost exist, line 8 picks one as the optimal path and line 11 classifies the marking in the closed set. Then the other firing sequences of equal cost (but different length) for this marking are not considered anymore.

Example 9. For the marking ω = {p4 : 1, p α2 : 1} of the synchronous product given in Fig. 1c, two firing sequences compete for the minimization of the cost (in case that silent transition costs). Indeed both γ = ( , a), ( , b), ( , tau), (b, b) and γ = ( , a), ( , b), (b, ) have a cost of E -1 + E -2 + E -3 and reach the marking ω. Hence, when using markings only in the states, the algorithm picks one of the sequence as the optimal one and adds ω in the closed set. Later, it does not consider the other firing sequence. However, we saw in Example 7 that γ is better than γ by using the discounted cost function but it can go to the hatch in the reduced version.

With this reduction of the search space, the modified algorithm is not guaranteed any more to return the optimal discounted alignments, but the gain in runtime is extremely significant. Moreover, in practice, the loss of quality is very limited: we observed that the alignments found by the modified algorithm have very similar discounted cost than the optimal discounted alignments.

Process Model Exploration Along with Trace Exploration (noted A * P T D=E ) Finally, in order to speed up the exploration, the alignment algorithm can simulate the synchronous product without explicitly constructing it. The idea is to replace the markings of the synchronous product by the markings of the process model along with the position of the trace. For instance, marking {p4 : 1, p α2 : 1} of the synchronous product given in Fig. 1c is translated to ({p4 : 1}, 1) where {p4} is the marking in N and 1 the position in σ. Then the final state is (mf , |σ|). The predecessor function p of this algorithm is slightly different to obtain γ the sequence of moves. To insert a move in the alignment, the algorithm requires to determine it type by simply comparing the labels of the fired transition and the activity of the current position in the trace.

6 Experiments: Discounted Alignments as a Heuristic for Approximating Classical Alignments

This section aims at showing a comparison of quality and runtimes between the proposed version of alignments and existing ones. We first present general comparisons.

Then we stress on the impacts of the discounted parameter. Finally, we zoom on perticular cases and added other methods similar to our.

Comparison with respect to baselines

Inputs We experimented the algorithms for both artificial and real-life logs and the corresponding models. Artificial set is taken from [START_REF] Taymouri | Model and event log reductions to boost the computation of alignments[END_REF] and contains large models. For real-life logs, we used data given in the Business Process Intelligence Challenges from 2012 to 2020. We mined the process models of those logs with methods of the literature 3 . First, we applied a preprocessing method introduced by [START_REF] Fani Sani | Prototype selection based on clustering and conformance metrics for model discovery[END_REF] to extract good prototypes of the logs 4 . This preprossessing step allows us to obtain not perfectly fitting models when using miners, interesting for alignments comparison. In fact, the method aims a finding more precise models. Then, we launched two different discovery algorithms on the found prototypes: the inductive miner [START_REF] Sander | Discovering block-structured process models from event logs containing infrequent behaviour[END_REF] and the split miner 2.0 [START_REF] Augusto | Split miner: automated discovery of accurate and simple business process models from event logs[END_REF]. As the latter tool gives BPMN models, we use ProM plugins to transform them into Petri nets.

We computed the alignments on variants only, i.e., unique sequences of activities. This choice of using variants only allows to correctly compare the method's runtimes in case that one reduce the log to variants and not another one. Table 2 gives an overview of the inputs.

Implementation The two algorithms presented in the previous section have been implemented in a branch of pm4py 5 .

Comparison We compare our alignment results to the four current methods of the state-of-the-art implemented in pm4py which are: -the Dijkstra search on the Synchronous Product without heuristic (DSP ) [START_REF] Adriansyah | Aligning observed and modeled behavior[END_REF], -a Disjkstra that consumes less memory by using a similar idea of our second algorithm (DLM ), -an A*-based algorithm on the state-space of the synchronous product that incorporates an heuristic on reaching the final marking (A * SP mf ) [START_REF] Sebastiaan J Van Zelst | Tuning alignment computation: An experimental evaluation[END_REF] and -its less-memory version (A * LM mf ). To compare the Fig. 2: Input Description runtimes, we exclude log-based implementations and used the trace-based version to avoid the use of the parallelism between variants that can be added to any version at the case level. We recall notation of our methods A * SP D=E , for the version that uses the synchronous product, and A * P T D=E , for the second one that explores only the process model and the trace.

Results

The aim of this section is to compare the runtimes to compute the alignments and the quality of the obtained alignments. The quality of an alignment found by a heuristic method, is defined as the ratio (in %) between the classical cost (number of model or log moves) of the optimal alignment and the classical cost of the alignment found by the method. In Fig. 3a we give the quality of each method. Similarly, in Fig. 3b, each line shows the sum of the runtimes of alignment computations by a method, expressed in percentage of the runtime of the DSP method. We use DSP method, which is the Dijkstra-based algorithm, as a reference because it represents the complete alignment algorithm.

For instance, we see in Fig. 3b that the runtime of the DLM algorithm is 20% of the runtime of the DSP method. For our heuristic A * P T D = 2, the average runtime is around 10% of the reference method DSP (which corresponds to a gain of 90% of runtime), for an average quality between 90 and 85% of the optimal alignments.

We did not represent in the charts the runtimes for methods A * SP mf and A * LM mf (implemented in pm4py) since they are much higher than the others: A * SP mf ran up to 30 times longer than the DSP and A * LM mf up to 7 times longer. We invite the reader to find the results and scripts on github6 .

Influence of the Discount Parameter E on the Quality and Runtime

Fig. 3a shows that the quality decreases when the parameter E of the discounted cost function raises. However the gain in term of runtimes is high when E > 1. This small lost of quality is correlated to the gain of runtime that we observe in Fig. 3b.

(a) Quality of the alignments obtained by different methods. Quality is defined as the ratio (in %) between the classical cost (number of model or log moves) of the optimal alignment and the classical cost of the alignment found by the method. The first line is the baseline and present the optimal approach which has no loss in quality, i.e., we observe 100% of quality. In general, one can see that the loss of quality with our heuristics is rather limited. The output of those experiments is the correlation between the parameter E and the compromise between quality and runtime of alignments. For E = 1, one gets exact alignments but runtimes are slow. For higher E one can extract very fast alignments but the quality is reduced.

In another hand, we want to raise awareness on the method A * P T D = 1 which corresponds to the optimal alignment without the construction of the synchronous product. The method gives exact alignments for reduced runtimes. Method DLM also doesn't construct the synchronous product but we see in Fig. 3a that there is a lost of quality.

Comparison with similar approaches

Additive Comparisons The omission of ProM and other tool results in the previous section is due to the differences between the output formats which made difficult the comparison of quality and runtimes. However, in this section we zoom in particular cases, i.e., by running a log sequence only, thus making human interpretation possible. We add P N R the results given by the PNetReplayer package of [START_REF] Adriansyah | Memory-efficient alignment of observed and modeled behavior[END_REF] in ProM and REC ILP the results given by [START_REF] Taymouri | A recursive paradigm for aligning observed behavior of large structured process models[END_REF]. We present only our versions for E = 2 which provide fast results. Specific Inputs We choose 3 models and traces that have particular characteristics. First, we run the alignment between the first trace of BPI2020 rp log and model IM because this couple (BPI2020 rp , IM) gives the least differences between the methods (Fig. 4a). The model has only 2 parallelism patterns and no loop. Then, we run the alignment of the first trace of L5 and model M 5 where our method specifically works well (Fig. 4b). This model contains a concurrent pattern including 28 transitions and one loop. Finally we present an alignment of the fifth trace of L3 which is very long (215 activities) and its model which has many loops and many parallelism patterns (Fig. 4c).

The latter aims at showing the weakness of our method.

Results

From the three charts of Fig. 4, we observe that all the methods usually find perfect alignments. This conclusion is done with the y-axis. The x-axis shows the runtimes and has a logarithmic scale due to the large differences between the methods. Then, the charts give an overview of the gain/loss of runtime compared to the baseline DSP versus the loss of quality. Best methods are on the top left of the charts. For BPI2020 rp and L5, we see that our implementations noted A * SP D = 2 and A * T D = 2 neighbor method of ProM (noted P N R). The versions using less memory seem to be much less efficient sometimes even for less quality (see DLM for L3). The method REC ILP worked only for the second model. M 3 is too large for the Gurobi open source version and format of model 2020 rp is not accepted by the tool. Alignments of Fig. 4c highlights our weakness. Despite very fast results, the quality is only of 20% of the optimal one. This is explained by the parameter E. Due to the size of the trace (215) and thus the run, the high base of logarithm E and the loops in the model, the algorithms face a situation where all the markings have the same cost (E n where n is very large borders zero). We launched the same input for E = 1.1 and our method finds the optimal alignment.

Conclusion

In this paper, we present a novel cost function for alignments. By using the position of the moves, our discounted cost function penalizes deviations of business processes that appear at early stage of the process execution. While the first aim is to align prefixes first, we nicely see that the proposed discounted cost function gives a heuristic for classical alignments. We implemented two versions of an A*-based algorithm that incorporate this heuristic and we experimented with artificial and real-life logs. The outputs of the experiments clearly show that the lost of quality, in term of log and model moves, is correlated to the gain of runtimes. This is due to the parameter E of our discounted cost function that forces prefix-first alignments. The compromise between quality and runtime can easily be set by using this parameter.

As future work, we suggest to combine the discounted cost function with other heuristics used for alignments. Also, the idea of using a discounted cost for alignments may be more or less relevant depending on the application that one is targeting. Among the multiple applications of alignments in conformance checking, some may be more or less resilient to the little loss of quality that we accept when using heuristics. In some settings, even, the alignments obtained for our discounted cost function may be more relevant than classical alignments, typically when the application justifies to penalize early deviations more than late ones.

3 (

 3 c) Synchronous Product between N and σ. Transitions in purple correspond to the model moves, green transitions are the synchronous moves and yellow transitions the log moves.

Fig. 1 :

 1 Fig. 1: Synchronous Product for Alignments between N and σ that has the Marking Reachability Problem.

Example 1 .

 1 Fig 1 shows a process model (Fig.

Example 2 .

 2 The alignment ϕ = ( , a), (b, b), (c, c) between N of Fig. 1a and σ of Fig. 1b costs 1 and is optimal.

  Fig 1 shows the synchronous product for alignments of the process model N given in Fig. 1a and the log trace σ of Fig. 1b.

Example 4 .

 4 Let u = x, a, b and v = a, y, b . The discounted edit distance between u and v is D u,v E = E -1 + E -3. If E = 1, the distance equals to 2 and is the Levenshtein edit distance where deleting x costs 1 and adding y costs 1.

Example 5 .

 5 For the alignment ϕ = ( , a), (b, b),

Example 6 .

 6 In Example 1, we saw that the optimal alignment by using the classical alignment cost function between σ = b, c and the model N of Fig. 1a is ϕ = ( , a), (b, b), (c, c) of cost 1. However, by using the discounted cost function with E = 2, optimal alignments are of ϕ = (b, b), ( , d), ( , e), ( , τ ) and ϕ = (b, b), ( , e), ( , d), ( , τ ) of cost 2 -2 + 2 -3 . This is due to the position of the move ( , a) in ϕ which is extremely costly.

Algorithm 1 :

 1 Computation of Optimal Alignments for the Discounted Cost Function (A * SP D=E )

  (b) Runtime (in % of the runtime of the DSP Algorithm). A percentage lower than 100 corresponds to a gain of runtime compared to the DSP method.

Fig. 3 :

 3 Fig. 3: Comparison of quality and runtimes of different methods.

Fig. 4 :

 4 Fig. 4: Particular alignments that draws advantages and disadvantages of our methods. Like above, DSP is the baseline.

  Output: d( m f , |γ| ), γ

			Get the current cost of reaching
		state
	18
	19	if c < d( m , i + 1 )	If current cost is better than known cost
	20	then
	21	d( m , i + 1 ) ← c	Update distance function
	25 Function h(t, i, E):
	26	if t is a synchronous move then
	27	return 0
	28	else
	29	return E -i	Discounted cost

} Add state to the closed set 12 X ← X \ { m, i } Remove state to the open set 13 for t ∈ T with m[t m do 14 if m , i + 1 ∈ A Reaching a state not yet visited 15 then 16 X ← X ∪ { m , i + 1 } Add state to the open set 17 c ← d( m, i ) + h(t, i + 1, E) 22 p( m , i + 1 ) ← (t, m, i )) Update predecessor function 23 24 γ ← t 0 , . . . , t n such that

t n = # 1 (p( m f , |γ| )), t n-1 = # 1 (p(# 2 (p( m f , |γ| )))) etc.

until the initial state m 0 , 0 is reached recursively.

available at https://github.com/BoltMaud/A-Discounted-Cost-Function-for-Fast-Alignmentsof-Business-Processes-Sources

[START_REF] Vincent Bloemen | Maximizing synchronization for aligning observed and modelled behaviour[END_REF] Prototype Selection plugin of Prom software with default

settings 5 currently available at https://github.com/BoltMaud/pm4py-core

available at https://github.com/BoltMaud/A-Discounted-Cost-Function-for-Fast-Alignmentsof-Business-Processes-Sources


Mathilde Boltenhagen
email: boltenhagen@lsv.fr

Thomas Chatain
email: chatain@lsv.fr

Josep Carmona
email: jcarmona@cs.upc.edu

An A*-Algorithm for Computing Discounted Anti-Alignments in Process Mining

Keywords:

Process mining techniques aim at analyzing and monitoring processes through event data. Formal models like Petri nets serve as an effective representation of the processes. A central question in the field is to assess the conformance of a process model with respect to the real process executions. The notion of anti-alignment, which represents a model run that is as distant as possible to the process executions, has been demonstrated to be crucial to measure precision of models. However, the only known algorithm for computing anti-alignments has a high complexity, which prevents it from being applied on real-life problem instances. In this paper we propose a novel algorithm for computing anti-alignments, based on the well-known graphbased A ⇤ scheme. By introducing a discount factor in the edit distance used for the search of anti-alignments, we obtain the first efficient algorithm to approximate them. We show how this approximation is quite accurate in practice, by comparing it with the optimal results for small instances where the optimal algorithm can also compute anti-alignments. Finally, we compare the obtained precision metric with respect to the state-of-the-art metrics in the literature for real-life examples.

I. INTRODUCTION

As event data becomes a ubiquitous source of information, data science techniques represent an unprecedented opportunity to analyze and react to the processes that generate these data. Process Mining is an emerging field that contributes to this aim [START_REF] Van Der Aalst | Data science in action[END_REF].

Process mining proposes algorithms for discovering process models (e.g., Petri nets) from event logs, or assessing the adherence of a process model in describing the traces found in an event log. The later is known as Conformance Checking, and is one of the central pillars of the field [START_REF] Carmona | Conformance Checking -Relating Processes and Models[END_REF].

Comparing a possibly infinite language (i.e., the process model may accept an infinite set of runs) with respect to a finite language (the event log is a finite set of traces) makes conformance checking techniques challenging. The notion of anti-alignment [START_REF] Chatain | Anti-alignments in conformance checkingthe dark side of process models[END_REF], [START_REF] Chatain | Antialignments-measuring the precision of process models and event logs[END_REF], however, aims at aiding this comparison, since it explores the process model to find a run that deviates the most with respect to all the traces in the event log. Anti-alignments can be used for several purposes, e.g., evaluating the precision/generalization of a process model with respect to an event log [START_REF] Van Dongen | A unified approach for measuring precision and generalization based on anti-alignments[END_REF], or log-based simulation of a process model. For instance, for the model and log shown in Fig. 1, an optimal anti-alignment is hb, e, d, ⌧ i (where ⌧ holds for silent activity).

Still, anti-alignments are hard to compute. The only published algorithm for computing alignments is grounded on encoding the problem as a SAT instance [START_REF] Boltenhagen | Optimized sat encoding of conformance checking artefacts[END_REF], thus making the algorithm not applicable for large, industrial problem instances.

This paper proposes a novel algorithm to fight the complexity of computing anti-alignments. We consider a rather simple, yet powerful idea that is motivated from the following use case: for certain processes, the costs associated to deviations at early stages of the process' execution are more important than the ones at the end. For instance, this situation appears in knock-out processes [START_REF] Van Der Aalst | Re-engineering knock-out processes[END_REF], where two outcomes are possible: OK or NOK. As the tasks of those processes aim at determining the final output, checks of the task are usually ordered in a growing order to allow fast decisions [START_REF] Reijers | Best practices in business process redesign: an overview and qualitative evaluation of successful redesign heuristics[END_REF].

Having this in mind, one can instantiate an A ⇤ algorithm to make the cost function exponentially biased to this use case: giving more importance (higher costs) to the deviations that occur in early stages, and exponentially reducing the costs as the search algorithm progresses. This discounted cost function has been introduced in [START_REF] Boltenhagen | A discounted cost function for fast alignments ofbusiness processes[END_REF] for alignment where the aim is to relate a process model to single log trace. The work showed a large reduction in search space for a small loss of quality. When applying the idea to anti-alignments, we tackle a different problem because the search focuses on the counterpart of alignments, i.e., deviations are observed, and it considers the whole log. However, the overall idea is similar. It provides a huge impact on the size of the search space required for the A ⇤ search, since the cost asymmetry makes the search space to rapidly shrink after the first steps are made.

Although the resulting algorithm is not guaranteed to provide optimal anti-alignments in general (i.e., maximally deviating model runs), the obtained implementation represents the first feasible attempt to compute anti-alignments for reallife problem instances. Although approximating the problem, in practice it can produce optimal results: for instance, the new algorithm can also provide anti-alignment hb, e, d, ⌧ i for the example of Fig. 1.

The paper is organized as follows: next section contextu-alizes the problem. In Section III the necessary background is detailed. Sections IV and V present the discounted cost function and the A ⇤ algorithm, respectively. In Section VI, we explain how we adapt the precision measure. Then in Section VII we report the experimental evaluation in different dimensions, whilst Section VIII concludes the paper.

II. RELATED WORKS

Anti-alignments have been introduced by [START_REF] Chatain | Anti-alignments in conformance checkingthe dark side of process models[END_REF] as the dark side of process models. The same year, the authors present in [START_REF] Van Dongen | A unified approach for measuring precision and generalization based on anti-alignments[END_REF] how those conformance artefacts can be used for measuring precision but also generalization, i.e., two fundamental metrics still in elaboration in process mining [START_REF] Van Der Aalst | Data science in action[END_REF]. Anti-alignments have been proposed for both the Hamming distance and the Levenshtein distance [START_REF] Chatain | Antialignments-measuring the precision of process models and event logs[END_REF]. Nicely, anti-alignment based precision metrics satisfy the necessary axioms for a precision metric [START_REF] Tax | The imprecisions of precision measures in process mining[END_REF]. Levenshtein distance is preferred, since it provides a more precise characterization of a deviation. Anti-alignments are the counterpart of alignments [START_REF] Adriansyah | Alignment based precision checking[END_REF]. Given a log trace, an alignment is a run of a process model as similar as possible in terms of distance. While many optimizations exist for alignment computation [START_REF] Lee | Recomposing conformance: Closing the circle on decomposed alignment-based conformance checking in process mining[END_REF]- [START_REF] Taymouri | Computing alignments of wellformed process models using local search[END_REF], none of them has been adapted to compute anti-alignments since for the later, the whole log and not only one single trace needs to be considered. Today, the only known implementation for Levenshtein based anti-alignments is a SAT encoding given by [START_REF] Boltenhagen | Optimized sat encoding of conformance checking artefacts[END_REF] which is limited to small instances.

Since the main use of anti-alignments is the computation of precision, we now provide an overview of the current methods for this in the field. The work of [START_REF] Rozinat | Conformance checking of processes based on monitoring real behavior[END_REF] is one of the first attempts to evaluate the precision of a process model with respect to an event log. It is grounded on comparing relation matrices from the model and log. Since it requires the full state-space exploration of the process model, it is only applicable to small models. In [START_REF] Munoz-Gama | Conformance checking and diagnosis in process mining[END_REF] deviations are estimated by the number of escaping arcs, i.e., runs of process models that deviate from the log. The state-space exploration of this method is bounded by the log behaviors. However, this work does not consider the size of the deviations, i.e., escaping arcs might cause large deviant behaviors.

As reported in [START_REF] Tax | The imprecisions of precision measures in process mining[END_REF], the two works above fail at satisfying important axioms for a precision metric. We now turn the focus to recent proposals that, as the case for anti-alignment based precision, do satisfy the reference axioms for precision.

[17] transforms recorded and modeled behaviors into an abstraction called directly follows automaton, and compares their languages. By introducing the notion of language quotients according to a measure, a precision metric can be defined, which is the ratio of common sequences between the log and the model to the total model runs. To deal with infinite languages, they use the topological entropy of languages, detailed in [START_REF] Ceccherini-Silberstein | On the entropy of regular languages[END_REF]. However this technique is very strict when any sequence is shared by the log and the model. In [START_REF] Kalenkova | A spectrum of entropy-based precision and recall measurements between partially matching designed and observed processes[END_REF], they add skips actions to make the approach more flexible. Finally, the work of [START_REF] Augusto | Abstract-and-compare: A family of scalable precision measures for automated process discovery[END_REF] is based on Markovian abstractions. By comparing the k-th order Markovian abstraction of a process model against the respective one of an event log, a precision metric can be obtained. Both works above represent an interesting attempt to estimate precision, but due to being grounded in sometimes aggressive abstractions, they fail in generating concrete insights pinpointing the real deviations. In contrast, anti-alignments are not based on abstraction but instead in concrete model runs, that may serve as a concrete explanations for repairing precision problems in a process model.

III. PRELIMINARIES

Event data can be represented by sequences of activities, i.e., traces, contained in logs defined as follows.

Definition 1 (Log). Let ⌃ be a set of activities. We define a log L as a finite multiset of log traces 2 ⌃ ⇤ . Thanks to discovery techniques [START_REF] Augusto | Split miner: automated discovery of accurate and simple business process models from event logs[END_REF], [START_REF] Leemans | Discovering block-structured process models from event logs containing infrequent behaviour[END_REF], one can obtain a process model from a log. Process models are often defined as Petri nets, which provide representations for causality, concurrency and loop behaviors.

ha, b, ci hb, d, ei he, di (a) Log L p 0 b t 1 a t 2
Definition 2 (Petri Nets as Process Models). A labeled Petri net [START_REF] Murata | Petri nets: Properties, analysis and applications[END_REF] is a tuple N = hP, T, F, m 0 , m f , ⌃, i, where P is the set of places, T is the set of transitions (with P \ T = ;), F ✓ (P ⇥ T ) [ (T ⇥ P ) is the flow relation, m 0 is the initial marking, m f is the final marking, ⌃ is an alphabet of actions and : T ! ⌃ [ {⌧ } labels every transition by an activity or as silent.

Semantics.: The semantics of Petri nets are given in term of firing sequences. Given a node x 2 P [ T , we define its pre-set

• x def = {y 2 P [ T | (y, x) 2 F } and its post-set x • def = {y 2 P [T | (x, y) 2 F }.
A marking is an assignment of a non-negative integer to each place. A transition t is enabled in a marking m when all places in • t are marked and can fire by removing a token from each place in • t and putting a token to each place in t • . A marking m 0 is reachable from m if there is a sequence of firings ht 1 . . . t n i that transforms m into m 0 , denoted by m[t 1 . . . t n im 0 . The set of reachable markings from m 0 is denoted by [m 0 i. A full run of a Petri net N is a firing sequence m 0 [t 1 . . . t n im f from the initial marking m 0 to the final marking m f . A Petri net is easy sound [START_REF] Adriansyah | Memoryefficient alignment of observed and modeled behavior[END_REF] if it has at least one full run, i.e. m f is reachable from m 0 . In this paper we assume easy sound Petri nets and note Runs(N ) the set of full runs of a process model N .

Example 1. Fig. 1 shows a log and a proposed, not optimal, process model. The initial marking m 0 is {p 0 } and the final marking is {p 7 }. Full runs Runs(N ) of the process model are the firing sequences ht 1 , t 3 , t 4 , t 6 i, ht 1 , t 4 , t 3 , t 6 i and ht 2 , t 5 , t 7 i which give modeled behaviors hb, e, d, ⌧ i, hb, d, e, ⌧ i and ha, b, ci.

To alleviate reading, we write the modeled sequences directly with the labels of the transitions in the rest of the paper.

Quality of process models is the core interest of conformance checking. In this paper, we focus on precision, a criterion that aims at quantifying how much extra modeled behavior is given by a process model and does not appear in the event log [START_REF] Van Der Aalst | Data science in action[END_REF].

One method to formalize precision is based on the most deviant full runs of process models called anti-alignments.

Definition 3 (Anti-alignment). Given a log L and a model N , an anti-alignment is a full run of N given modeled sequence such that it maximizes the minimal distance min 2L dist( , ) to the log, where dist is a distance between sequences.

Common distance used in Process Mining is a version of the Levenshtein edit distance.

Definition 4 (Levenshtein Edit distance). The Levenshtein Edit Distance L(u, v) between two sequences u and v 2 ⌃ ⇤ is the minimal number of edits (deletions or insertions) needed to transform u into v.

8 > > > > > > > > < > > > > > > > > : L(hi, hi) = 0 L(u, hi) = |u| L(hi, v) = |v| L(a.u 0 , b.v 0 ) = L(u 0 , v 0 ) if (a == b) L(a.u 0 , b.v 0 ) = min ( L(a.u 0 , v) + 1, L(u, b.v 0 ) + 1 otherwise.
Example 2. For log L of Fig. 1 and the presented process model N , the full run hb, e, d, ⌧ i is an anti-alignment and is at distance 1 or more to any log sequence.

For models with executable loops, which produce long runs arbitrarily far from the associated log, no run maximizes the distance to the log. However, such long runs, although far from the log, are less relevant for measuring precision than shorter runs diverging from the log. Following this idea, a parameter ✏ is introduced in the definition of anti-alignments in order to penalize long runs as follow: sup

2Runs(N ) min 2L dist( , ) (1+✏) | | . We denote with L ✏ ( , ) = L( , ) (1+✏) | | the corresponding adaptation of Levenshtein distance.
Definition 5 (Anti-Alignment based Precision). For an event log L and a model N , ✏-precision P ✏ aa (N, L) [START_REF] Chatain | Antialignments-measuring the precision of process models and event logs[END_REF] is defined by:

P ✏ aa (N, L) def = 1 sup 2Runs(N ) min 2L ✏ ( , ) (1)
with ✏ ( ,

) def = L✏( , ) | |+| | and ✏ 0.
Precision metric ranges between 0 (imprecise models) and 1 (precise models).

IV. A DISCOUNTED EDIT DISTANCE FOR PREFIX-BASED ALIGNMENT OF ACTIVITIES

Due to the complexity of recorded logs, process models tend to be large and contain a lot of choice, concurrency and loop behaviors. Naive exploration of the runs of a model has to consider a huge number of candidates for anti-alignments.

The aim of this paper is to reduce this exploration by using the discounted edit distance introduced in [9] which assigns higher costs to edits that appear at the beginning of the sequences. Definition 6 (Discounted Edit Distance). We define the Discounted Edit Distance between two sequences u and v with discount parameter ✓ 1 by

D ✓ (u, v) def = D 0 ✓ (u, v) where: 8 > > > > > > > > < > > > > > > > > : D k ✓ (hi, hi) = 0 D k ✓ (hi, b.v 0 ) = D k+1 ✓ (hi, v 0 ) + ✓ k D k ✓ (a.u 0 , hi) = D k+1 ✓ (u 0 , hi) + ✓ k D k ✓ (a.u 0 , b.v 0 ) = D k+2 ✓ (u 0 , v 0 ) if (a == b) D k ✓ (a.u 0 , b.v 0 ) = min ( D k+1 ✓ (u 0 , v) + ✓ k D k+1 ✓ (u, v 0 ) + ✓ k otherwise.
Hence, insertions and deletions cost ✓ k where k refers to the position where they occur.

For ✓ = 1, the Discounted Edit Distance is the Levenshtein distance. However, for larger values of ✓, edits at the beginning of the sequences are more costly than edits at the end because of the exponent k based on the position of the edits.

By assigning higher costs to edits at the beginning of the sequences, the discounted parameter ✓ allows one to select efficiently prefixes of runs which may be continued to promising anti-alignments. Then revelant values for ✓ are slightly larger than 1 and close to 1 if the purpose is to approximate the Levenshtein edit distance.

Example 4. For instance, for ✓ = 2, an edit at position k costs more than the sum of all next edits of position k 0 > k. Let L 0 = {hb, ci, hb, d, f i} be another log less conforming with process model N of Fig. 1. The best anti-alignment for L 0 and N is ha, b, ci which is strongly more deviant in the beginning of the run with activity a. Its minimal distance to the log is ✓ 0 = 1 and cannot be topped to another run despite summing edits. However, for lower values of the discounted parameter ✓, like ✓ = 1.10, the distance finds modeled behavior hb, e, d, ⌧ i as the furthest one from the log L 0 , like when using the Levenshtein edit distance.

V. AN A*-BASED ALGORITHM FOR COMPUTING DISCOUNTED ANTI-ALIGNMENTS

To get anti-alignments of a process model N and a log L using the discounted distance, we present an A*-based algorithm given in Alg.1 that replays the firing sequences of the process model in order to find a full run such that :

sup 2Runs(N ) min 2L D ✓,✏ ( , ) (2)
where D ✓,✏ ( , ) = D ✓ ( , ) (1+✏) | | to penalize long runs in case of loops in N .

The algorithm maintains a priority queue of prefixes of runs, implemented as a heap of tuples hm, , di, where is the prefix, m is the state that it reaches, and d is the priority with which it should be treated. This priority d is defined as the quantity:

h ✓,✏ ( , L) def = min 2L ✓ D ✓,✏ ( , ) + ✓ | | | | ✓ 1 ◆ (3)
that bounds from Eq. 2 the value min 2L D ✓,✏ ( 0 , ) that any full run 0 having as prefix can achieve.

New prefixes are obtained by firing the transitions of the process model (line 14 of Alg.1) and the algorithm terminates when the queue is empty or no candidate prefix can improve the best value obtained so far (line 8).

Algorithm 1: Computation of Anti-Alignment using the Discounted Distance

Input : N = (P, T, F, , m 0 , m f ): process model, L: log, ✓: discount parameter, ✏: long run limit parameter

A. Proof of optimality

Let us first prove the announced fact: for every full run 0 having as prefix, h ✓,✏ ( , L) min 2L D ✓,✏ ( 0 , ). Let , 0 = .u and , we show that D ✓,✏ ( ,

) + ✓ | | | | ✓ 1 D ✓,✏ ( 0 ,
). This is because, in order to edit 0 to , one can edit its prefix to (at cost D ✓,✏ ( , )) and then delete the letters of u one by one. The first deletion costs

✓ | | | | 1 , the second one ✓ | | | | 2 .
. . and the sum of these costs is bounded by

P 1 i=1 ✓ | | | | i = ✓ | | | | ✓ 1
. The algorithm satisfies the following invariant, which holds before and after each iteration of the while loop: either the current best value is optimal or every optimal anti-alignment has a prefix in the queue Q. It is preserved at each iteration for the following reason. Let hm, , di pop from Q and assume is the prefix of an optimal full run 0 . Either 0 = (then min 2L D ✓,✏ ( , ) is compared with B ) or 0 has a prefix of the form .t, which is queued. The while loop is broken (line 8) only when d  B . As stated before, this implies that no 0 having as prefix will beat the current best value; and this also holds for all the other prefixes remaining in the queue since their value is smaller than d.

Termination: once B > 0, any longer than

log ✓ (✓ 1)B log(1+✏)
popped from Q breaks the while loop. Indeed, this implies

(1 + ✏) | | ✓ (✓ 1)B . Moreover, for every , D ✓ ( , )  P 1 i=0 ✓ i = ✓ ✓ 1 ; hence D ✓,✏ (
, )  B Since only finitely many prefixes are shorter, and no prefix is queued twice, the termination of the algorithm is guaranteed as soon as B > 0, i.e. a full run 6 2 L has been found.

B. Complexity Analysis

The proof of termination above also gives us the time complexity of our algorithm: in the worst case, it explores all prefixes strictly shorter than l def = log ✓ (✓ 1)B log(1+✏) , and there may be up to

1+|T |+|T | 2 +• • •+|T | l = |T | l+1 1
|T | 1 such prefixes. (In this expression |T | can be replaced by the maximum branching degree of a reachable marking, i.e. the maximum number of transitions enabled together at a reachable marking.) Observe represents an infinite language of its transition labels which are all connected to the same place. We choose those models to present a normal case versus a complex and imprecise model.

In Tab.Ia, we show how changing the discounted parameter ✓ can improve the runtime. For large ✓, prefixes cost more than suffixes, thus allowing the algorithm to considerably reduce the exploration. This aspect appears very clearly for the flower model.

The anti-alignments found for the flower model are not long because of the parameter ✏ set to 0.01. Then we observe that the found precision is quite high for this model which is very imprecise. By setting ✏ to larger values, we would get longer anti-alignments, thus providing more significant value of precision. However, due to the possible combinations of longer runs, the algorithm would blow up.

Tab.Ib aims at showing the benefit of the limit µ on the number of explorations of prefixes reaching the same marking. We see that for ✓ = 1.5 and ✏ = 0.01, the runtime of computing an anti-alignment for the flower model is divided by 10 when setting µ to 100. The runtime improvement by using µ is prominent and allows to explore longer runs (for instance Tab.Ib shows a result where ✏ = 0.001). Finally, the last line of Tab.Ib presents an experiment where µ is very small and still provides a relevant anti-alignment (just a bit shorter).

There seems to be some parameter settings that work well for the type of instances we have used, but it still needs to be investigated how to adapt the parameters for arbitrary models and logs. We propose to set µ from 5 to 10 to limit the number of times the algorithm reaches the same state. This limitation is efficient for choice structures as the best paths are usually crossed first. For parallel structures, states are mainly different and this parameter does not help to tackle those complex patterns. Regarding ✓, our experiments suggest to set it to a value between 1.1 (for better quality) and 1.5 (for faster result). Finally, ✏ can be set to 0.01 which already gives good approximations of model precision, but for more precise results we advise to drop this value to 0.001 which allows to observe longer runs.

B. Anti-alignments Comparison on Artificial Logs and Models

Now that we have presented the approximation impacts, we take advantage of them and compare our results to the optimal results for all artificial models associated to L 00 where the SAT implementation of [START_REF] Chatain | Antialignments-measuring the precision of process models and event logs[END_REF] can also compute the anti-alignments. To compute exact precision (column E.P ✏ aa of Tab.II) their algorithm solves several SAT formulas by increasing the size of the run until the anti-alignment converges. Because the process is slow, they propose another version in which one can set the size of the run if it is known. In Tab.II, we decided to compare runtimes of anti-alignment computation and we used the latter version. We set the size of the run to 11 which is the minimal size to get a full run for all the models. [START_REF] Chatain | Antialignments-measuring the precision of process models and event logs[END_REF] where the maximal size of the run n = 11. Column E.P ✏ aa shows the optimal anti-alignment precision where ✏ = 0.01 Column P ✏ aa gives the approximations of the precision given by both the shorter version of [START_REF] Chatain | Antialignments-measuring the precision of process models and event logs[END_REF] (lines L n for Levenshtein with a size of the run n to 11) and the proposed algorithm of this paper (lines D ✓,✏ where ✓ = 1.5 and ✏ = 0.01 and heuristic µ = 10).

Observations are significant: the novel algorithm runs much faster and obtains, in most times, the optimal results. Differences between the found anti-alignments can be explained by the parameters. For instance, by using the flower model, our discounted version D ✓,✏ returns a shorter run due to parameter µ which strictly reduces the number of times the algorithm can reach a marking.

The big difference observed for the model entitled C,F equal loop, for which our algorithm finds a much worse antialignment, is due to the fact that this model is not safe 2 , i.e., transitions labeled with C and F output a token in their input place, thus allowing running the transitions again. However, the SAT implementation does not consider unsafe Petri nets 2 A Petri net is safe if every place can have at most one token in any reachable marking.

(it restricts their behavior to runs visiting only safe markings), and, hence, cannot guarantee optimality for this model. The precision obtained with D ✓,✏ is then more accurate than E.P ✏ aa . Finally, we observe that the All parallel model, whose transitions are all concurrent, is much slower than all other models by using our A*scheme. In this model, the limit µ does not have any impact because the markings are different for all combinations of firing transitions. Also ✓ = 1.5 is not too strict and many prefixes are explored. However, the runtime for this model is still faster than the fastest version of [START_REF] Chatain | Antialignments-measuring the precision of process models and event logs[END_REF].

C. Precision of Real-life Models

In this section, we present, for the first time, anti-alignment based precision on real-life models whose description can be found in Tab. III. Those models have been discovered from the prototypes of the logs defined by [START_REF] Fani Sani | Prototype selection based on clustering and conformance metrics for model discovery[END_REF] and by using the inductive miner (IM) [START_REF] Leemans | Discovering block-structured process models from event logs containing infrequent behaviour[END_REF] and the split miner (SM) [START_REF] Augusto | Split miner: automated discovery of accurate and simple business process models from event logs[END_REF] 3 . We recall that the previous SAT implementation of anti-alignment could not deal with entire large logs due to the complexity of the encoding. We show both computation time and precision measure in Tab. IV and compare our work to the ET C measure defined by [START_REF] Adriansyah | Alignment based precision checking[END_REF], the M AP 3 measure of [START_REF] Augusto | Abstract-and-compare: A family of scalable precision measures for automated process discovery[END_REF] and the EM P measure proposed by [START_REF] Kalenkova | A spectrum of entropy-based precision and recall measurements between partially matching designed and observed processes[END_REF], all introduced in the related works. We remark than any precision measure agrees for all the inputs which strengthens the interest of research about this metric in process mining. The M AP 3 measure finds a perfectly precise model, i.e., the IM model of BPI2019 log. Nicely, our method has a similar precision, 0.934, but found an anti-alignment for this model which can figures the language difference between the log and model. The EM P measure is stricter with a precision of 0.468. For this log, ET C precision of [START_REF] Adriansyah | Memoryefficient alignment of observed and modeled behavior[END_REF] lasts more than several hours so we stopped the process. This method uses alignments whose complexity is related to the log complexity. As we can see in Tab.III, the BPI2019 log is the more complex log with 251 734 cases and 42 different type of activities.

Our method also has to deal with log complexity. More than 75% of our runtime presented in Tab.IV is used to compute the discounted distances. For the IM model of BPI2020 rp , our method also takes several hours. This model contains two parallel structures of 10 and 2 transitions, which make the search space explode. But in several cases, our method even gives the fastest runtime.

Besides runtimes, it is not obvious to conclude which precision metric is more valuable. However, as a conclusion of this section, we want to point out that, in order to understand the precision of process models, a human requires more than a numerical value. We believe that anti-alignment is the added value of our approach because it provides explanation for the imprecision of models. In the same way as in model checking a counterexample trace is used to show the violation of a property for a particular system, anti-alignments show traces that the user can understand and which show a model behavior that justifies a particular precision problem. In the extreme case, a very imprecise model will be easily understood via its very deviating anti-alignments.

VIII. CONCLUSION

In this paper, we show the advantage of a discounted distance to reduce the search space for finding anti-alignment of a process model w.r.t. an event log. Thanks to an A*-based algorithm that prioritizes promising prefixes, we find the optimal anti-alignments by using discounted costs slightly higher than 1 which, in practice, approximates well the Leventsheinbased anti-alignments. We show through several experiments that our algorithm outperforms state-of-the-art methods for computing anti-alignments. Moreover, we see, for the first time, anti-alignment based precision for real-life instances.

In the real-life experiments, our algorithm hits a limit for a process model exhibiting high concurrency. Future work should target heuristics for this specific situation.

Fig. 1 :

 1 Fig. 1: A log L and a Petri Net as Process Model

Example 3 .

 3 For ✏ = 0.01 and L and N of Fig.1, we have P ✏ aa (N, L) 88 for = hb, e, d, ⌧ i and = he, di.

Example 5 .

 5 This example illustrates the use of the fraction ✓ | | | | ✓ 1 in the definition of h ✓,✏ . Let ✓ = 1.10 and ✏ = 0 for log L 0 = {hb, ci, hb, d, f i} and model N of Fig.1. The open set Q contains, at some point, states h{p 1 , p 2 }, hbi, d b i and h{p 3 }, hai, d a i of concurrent prefixes hbi and hai. Let's try to consider only their distance to the log, i.e., d b = min 2L D 1.10,0 (hbi, ) = 0.83 and d a = min 2L D 1.10,0 (hai, ) = 2.73. Prefix hai is the best current anti-alignment and the algorithm continues with this prefix (line 6) until the final marking. The final run is B = ha, b, ci and B = 1. Prefix hbi is then forgotten at line 7 because its current distance is lower than B . However, for ✓ = 1.10, the optimal anti-alignment is indeed hb, e, d, ⌧ i. By adding the fraction ✓ | | | | ✓ 1 in d b and d a given in function h at line 16 which prevents best suffixes, d b = 7.51 and prefix hbi is now handled at line 7 and becomes the best anti-alignment.

TABLE I :

 I Heuristic Impacts on Anti-alignments by Using the Discounted Distance D ✓

TABLE II :

 II Comparison of Anti-alignments and Precision on Artificial Log and Models. The discounted based method is noted by D ✓,✏ with ✓ = 1.5, ✏ = 0.01 and µ = 10 and L n is the fastest Levenshtein version of

TABLE III :

 III Real-life Logs and Models Description.

TABLE IV :

 IV Real-life Logs and Models Precision where the Anti-alignment Precision P ✏ aa is found with Discounting Antialignments and ✓ = 2, ✏ = 0.01, µ = 5

Available at https://github.com/BoltMaud/pm4py-core

The used models are available at https://github.com/BoltMaud/A-Discounted-Cost-Function-for-Fast-Alignments-of-Business-Processes-Sources/tree/main/model

that l is larger when B is small, i.e. the algorithm takes more time when the model is precise.

C. A Heuristic for Alg.1 to Further Reduce the Search Space

When models are dense in concurrency and loops, some markings are visited a large number of times. For instance, all possible combinations of a concurrent part finally reach the same marking. Because best prefixes are prioritized, a simple but efficient heuristic is to limit the number of times a marking can be reached. We propose a parameter µ for this purpose and observe very nice results in practice.

VI. PRECISION

The main purpose of finding anti-alignments is to compute precision of process models. The present paper provides an algorithm for finding anti-alignments not necessarily optimal, an artifact of reducing the search space. In return, the technique is able to work with real instances. Once an anti-alignment is found, one can use it to compute precision of its model by using the classical Levenshtein based precision as defined in Section III. The expression

of Def.5 is approximated by

for the run computed by Alg.1. In Eq. ( 5), might not be an optimal anti-alignment as it appears in Eq. ( 4). Its minimal distance to the log can be smaller than the optimal one for a given log and model. Thus, using Eq. ( 5) in precision computation gives an upper-bound of the exact anti-alignment precision of Def.5. Nicely, we observe perfect matching results for some instances in practice.

VII. EXPERIMENTS

The algorithm has been implemented in a copy of pm4py Python library 1 . In this section, we present a set of comparisons of the discounted distance based anti-alignment and precision with the state-of-the-art methods. The experiments have been run on a MacBook air 2017 model with a 1.8 GHz Intel ® Core TM i5 CPU and 8G RAM.

A. Comparison of the results obtained with the different heuristics

The aim of this first subsection is to present the risks and benefits of using the heuristics. For this purpose, we used the known artificial log

hA, C, D, H, F, Ii} and two of its associated models specifically chosen for showing the impact of the heuristics: the generating model and the flower model. The models can be found in [START_REF] Van Dongen | A unified approach for measuring precision and generalization based on anti-alignments[END_REF] page 4, [START_REF] Augusto | Abstract-and-compare: A family of scalable precision measures for automated process discovery[END_REF] and [START_REF] Chatain | Antialignments-measuring the precision of process models and event logs[END_REF] page 10.

The generative model has a finite set of runs obtained by its several choice structures. By contrast, the flower model


MD, PhD João Pedro Ferreira
email: j.ferreira@chru-nancy.fr

Omecamtiv Mecarbil: a Personalized Treatment for Patients with Severely Impaired Ejection Fraction

Omecamtiv mecarbil is a first-in-class "myotrope" that selectively binds to cardiac myosin increasing cardiac sarcomere function, which can lead to an improvement of myocardial contractility, particularly by augmenting the power stroke at the start of the systole and the contractile function of the atria. [START_REF] Vj | Mechanistic and structural basis for activation of cardiac myosin force production by omecamtiv mecarbil[END_REF][START_REF] Teerlink | Dose-dependent augmentation of cardiac systolic function with the selective cardiac myosin activator, omecamtiv mecarbil: a first-in-man study[END_REF] In the Chronic Oral Study of Myosin Activation to Increase Contractility in Heart Failure (COSMIC-HF) phase 2 trial, treatment with omecamtiv mecarbil for 20 weeks increased left ventricular systolic ejection time and stroke volume, reduced endsystolic and diastolic diameters, and decreased NT-pro BNP levels. [START_REF] Teerlink | Chronic Oral Study of Myosin Activation to Increase Contractility in Heart Failure (COSMIC-HF): a phase 2, pharmacokinetic, randomised, placebo-controlled trial[END_REF] These encouraging findings prompted the conduct of the phase 3 Global Approach to Lowering Adverse Cardiac Outcomes through Improving Contractility in Heart Failure (GALACTIC-HF) trial to test the efficacy and safety of omecamtiv mecarbil (vs. placebo) in patients with heart failure and a left ventricular ejection fraction (LVEF) of 35% or less. [START_REF] Teerlink | Omecamtiv Mecarbil in Chronic Heart Failure With Reduced Ejection Fraction: Rationale and Design of GALACTIC-HF[END_REF] GALACTIC-HF included 8256 symptomatic patients with elevated natriuretic peptide levels, who were randomized both in the hospital and in ambulatory settings and followed for a median of 22 months. The primary outcome, a composite of a first heart failure (HF) event (hospitalization or urgent visit for HF) or death from cardiovascular causes, occurred in 1523 of 4120 patients (37.0%) in the omecamtiv mecarbil group and in 1607 of 4112 patients (39.1%) in the placebo group, with a corresponding HR of 0.92; 95%CI, 0.86 to 0.99. The primary outcome rate reduction with omecamtiv mecarbil was due to reduction of HF events, without impact on cardiovascular mortality: HR, 1.01; 95%CI, 0.92-1.11. [START_REF] Teerlink | Cardiac Myosin Activation with Omecamtiv Mecarbil in Systolic Heart Failure[END_REF] Among the multiple subgroups tested (24 in total) LVEF (≤28% vs. >28%, median) showed a significant interaction for the effect of omecamtiv mecarbil on the primary outcome, whereby patients with a LVEF ≤28% could have benefited more from omecamtiv mecarbil therapy (vs. placebo) than patients with a LVEF >28%: HR, 0.86; 95%CI, 0.79 to 0.94 for patients with a LVEF ≤28% and HR, 1.04; 95%CI, 0.94 to 1.16 for patients with a LVEF >28%; interaction P =0.004. Atrial fibrillation (AFib, yes vs. no) was the other subgroup where a similar qualitative interaction was found, suggesting a greater benefit of omecamtiv mecarbil among patients in sinus rhythm compared with patients in AFib: HR, 0.86; 95%CI, 0.79 to 0.94 for patients in sinus rhythm and HR, 1.05; 95%CI, 0.93 to 1.18 for patients in AFib. [START_REF] Teerlink | Cardiac Myosin Activation with Omecamtiv Mecarbil in Systolic Heart Failure[END_REF] Beyond the directionally opposite effects, there is a strong biological plausibility suggesting that these interactions are not a product of chance. Omecamtiv mecarbil increases systolic stroke power and the atrial contractile function; therefore, it is plausible that the drug only benefits patients with a severely impaired LVEF in sinus rhythm, in whom the increment in ventricular and atrial contraction may produce a meaningful and beneficial impact on outcomes.

In this issue of the Journal, Teerlink J.R. and colleagues study in detail the influence of baseline LVEF on the therapeutic effect of omecamtiv mecarbil. Beyond the findings shown in the primary report, [START_REF] Teerlink | Cardiac Myosin Activation with Omecamtiv Mecarbil in Systolic Heart Failure[END_REF] the authors expand the analysis assessing the effect of omecamtiv mecarbil across quartiles and the continuous spectrum of LVEF; but unfortunately, they do not report the interplay between the LVEF and atrial rhythm. Given the qualitative treatment by LVEF and atrial rhythm interactions backed by the pharmacologic action of omecamtiv mecarbil on myocardial and atrial contractility, one might expect a most pronounced treatment effect among patients with a severely impaired systolic function in sinus rhythm.

Notwithstanding, it is interesting to observe that the treatment effect on the study primary outcome is similar between patients with a LVEF of 23% to 28% (HR, 0.85; 95%CI 0.74 to 0.97) and those with a LVEF ≤22% (HR, 0.83; 95%CI, 0.73 to 0.95), but very different than the treatment effect observed in patients with a LVEF of 29% to 32% (HR, 1.11; 95%CI, 0.96 to 1.28) and in patients with a LVEF ≥33% (HR, 0.99; 95%CI, 0.84 to 1.16); interaction P =0.013. Accordingly, the analysis with LVEF as a continuous covariate suggest that the beneficial effect of omecamtiv mecarbil is most pronounced among patients with a LVEF below 25%; interaction P =0.004 by LVEF as continuous variable. Omecamtiv mecarbil had no effect on cardiovascular (including sudden) or all-cause death, regardless of ejection fraction.

In GALACTIC-HF, the placebo primary outcome event-rates (per 100 patient-years) were 27.2 and 35.6 in patients with a LVEF from 23 to 28% and ≤22%, respectively; much higher than the event-rate of 20.0 seen in patients with a LVEF ≥33%. These subgroups, with a LVEF from 23 to 28% and ≤22%, experienced primary outcome relative reductions of 15 to 17%, and absolute reductions (per 100 patient-years) of 3.3 and 7.4. For example, twelve patients with a LVEF ≤22% need to be treated over a 3-year period to prevent one HF hospitalization. GALACTIC-HF enrolled more than 8200 patients of whom 4456 had a LVEF ≤28% and 1821 experienced a primary outcome event (within the LVEF ≤28% subgroup), providing enough power to assume a benefit only to patients with a severely Reduced) trials the total primary outcome events (composite of HF hospitalization or cardiovascular death) were less than half (888 and 823 patients, respectively) of the events experienced by patients with a LVEF ≤28% in GALACTIC-HF. [START_REF] Mcmurray | Dapagliflozin in Patients with Heart Failure and Reduced Ejection Fraction[END_REF][START_REF] Packer | Cardiovascular and Renal Outcomes with Empagliflozin in Heart Failure[END_REF] In an era where adding more treatments to the therapeutic armamentarium of patients with HFrEF is increasingly difficult, personalized treatment approaches are necessary to cover unmet needs, benefit patients who need the most, and also to be cost-effective and generate return of investment. [START_REF] Figtree | A call to action for new global approaches to cardiovascular disease drug solutions[END_REF] Ejection fraction (and atrial rhythm) are probably the best means to stratify and identify patients responsive to omecamtiv mecarbil in a manner that is completely aligned with the biological mechanisms of the drug and using widely available and inexpensive biomarkers (an echo-and electrocardiogram).

Based on LVEF as a continuous variable, the "sweet spot" where the effect of omecamtiv mecarbil begins to occur is below 25%; therefore, based on the large number of patients and events among those with severely impaired ejection fraction in GALACTIC-HF, omecamtiv mecarbil should be recommended to patients with a LVEF <25% to reduce HF hospitalizations.

Severely impaired systolic function (LVEF <25%)

Less impaired systolic function

Atrial fibrillation

  impaired systolic function. For comparison, in the Study to Evaluate the Effect of Dapagliflozin on the Incidence of Worsening Heart Failure or Cardiovascular Death in Patients With Chronic Heart Failure (DAPA-HF) and EMPagliflozin outcomE tRial in Patients With chrOnic heaRt Failure With Reduced Ejection Fraction (EMPEROR-

Figure 1 .

 1 Whether atrial rhythm should be part of the decisional algorithm should be explored in further studies.

Figure 1 .

 1 Figure 1. Omecamtiv mecarbil benefits patients with severely impaired ejection

JPF is a consultant for Boehringer-Ingelheim.