Process mining sheds new light on the relationship between process models and real-life processes. Process discovery can be used to learn process models from event logs. Conformance checking can be used to confront a descriptive or normative model with the actual behavior observed. Quantifying the relationship between process models and event logs is notoriously difficult. Existing approaches seem to make ad-hoc choices, leading to results that are not easy to interpret. To address these problems, we present 21 conformance propositions. These describe expected or desired properties of conformance measures. These cover notions such as recall (also called fitness), precision, and generalization. These propositions are put into a broader frame of Log-to-Log (L2L), Model-toModel (M2M), and Log-to-Model (L2M) comparisons. Moreover, it is argued that conformance measures need to consider the likelihood of traces. Real-life event logs are incomplete showing only sample behavior. Moreover, observed traces tend to follow a Pareto distribution. Yet, mainstream process mining approaches stick to a “binary view” on process models (observed traces are fitting or not). This is hindering progress. The goal is to trigger a discussion by clearly formulating the challenges and requirements (rather than proposing new measures or techniques).
21 Conformance Propositions
In process mining, there are two main types of artifacts: event logs and process models
[
L2L
L2M play-in (discover)
L2M play-out (simulate) (b) Scenario 2 play-out (simulate)
L2M
L2M play-in (discover) process model process model event log process model event log to discover a process model that is subsequently used to produce another event log. The original and the generated event logs can be compared using an L2L (Log-to-Log) assessment.
Event logs only contain example behavior. This not only makes process discovery
challenging; it is also difficult to assess the quality of the process model in relation to
the log. Since process mining focuses on the relationship between observed behavior
and modeled behavior (i.e., L2M assessments), it is important to quantify the
relationship between an event log l ∈ L and a process model m ∈ M. This is reflected by
the different conformance measures that have been proposed [
This paper does not aim to provide concrete conformance measures (although some examples are given). Instead, the focus is on characteristic/desired properties of such measures. We propose 21 conformance propositions, i.e., properties that recall, precision, and generalizations measures could or should satisfy for any model and log combination.1 Researchers and developers creating new measures should be clear on what conformance propositions they aim to support and ensure that the implemented measures support these. Users of existing conformance measures should be aware of seemingly obvious conformance propositions that are violated by existing approaches.
Next to defining 21 conformance propositions, this paper provides two additional contributions. First of all, we provide a more holistic perspective on the challenges related to comparing models and logs. Second, we show that probabilities play a key role in such definition. The likelihood of traces in models and the frequency of traces in logs are key elements that should not be ignored.
It is important to note that this paper focuses on trace-based control-flow-oriented conformance measures, i.e., we abstract from other event attributes (resources, products, time, costs, etc.) and consider full traces (not local patterns). This scope is clearly limited. However, it helps to focus the discussion.
The remainder is organized as follows. Section 2 presents some preliminaries. Next to event logs also process models which define trace likelihoods are defined. Sections 3, 4, and 5 discuss L2L (Log-to-Log), M2M (Model-to-Model), and L2M (Log-to-Model) comparisons and define example measures. Section 6 describes the 21 conformance propositions. Section 7 reflects on the conformance propositions using the simple measures defined in sections 3, 4, and 5. Section 8 discusses the viewpoint used in the paper and possible alternative viewpoints. Section 9 concludes the paper. 2
Process mining techniques focus on the relationship between observed behavior and modeled behavior. Therefore, we first formalize event logs (i.e., observed behavior) and process models (i.e., modeled behavior). To do this, we consider a very simple setting where we only focus on the control-flow, i.e., sequences of activities. However, unlike most other papers, we attach probabilities to traces. 2.1
The starting point for process mining is an event log. Each event in such a log refers to
an activity possibly executed by a resource at a particular time and for a particular case.
An event may have many more attributes, e.g., transactional information, costs,
customer, location, and unit. Here, we focus on control-flow. Therefore, we only consider
activity labels and the ordering of events within cases.
1 The Merriam-Webster dictionary defines the noun proposition as “an expression in language
or signs of something that can be believed, doubted, or denied or is either true or false” [
Trace t = ha, b, c, d, ci ∈ T refers to 5 events belonging to the same case (i.e., |t| = 5). An event log is a collection of cases each represented by a trace. Definition 2 (Event Log). L = B(T ) is the universe of event logs. An event log l ∈ L is a finite multiset of observed traces. τ (l) = {t ∈ l} ⊆ T is the set of traces appearing in l ∈ L. τ (l) = {t ∈ T | t 6∈ τ (l)} is the complement of l, i.e., non-observed traces.
An event log is a multiset of traces. Event log l = [ha, b, ci5, hb, a, di3, ha, b, di2] refers to 10 cases (i.e., |l| = 10). Five cases are represented by the trace ha, b, ci, three cases are represented by the trace hb, a, di, and two cases are represented by the trace ha, b, di. l(t) is the number of times t appears in l, e.g., l(hb, a, di) = 3. We assume that the usual operators are defined for multisets. l1 ] l2 is the union of two multisets, |l| is the number of elements, and l1 \ l2 is the difference. l1 ∩ l2 is the intersection of two multisets. Hence, (l1 ∩ l2)(t) = l1(t) max l2(t). [t ∈ l | b(t)] is the multiset of all elements in l that satisfy some condition b. l1 ≤ l2 means that l1 is contained in l2. For example, [a2, b] ≤ [a2, b2, c], but [a2, b3] 6≤ [a2, b2, c2] and [a2, b2, c] 6≤ [a3, b3].
τ (l) is the set traces that were not observed in the event log. Note that τ (l) and τ (l) partition the universe of traces T . 2.2
Often the behavior of a process model m is simply defined by the set of traces allowed by m. However, there may be vast differences in the likelihoods of traces. For many processes, the observed traces follow a Pareto distribution. Typically, there are a limited number of traces that can be observed frequently, while there are often much more traces that are infrequent.
Actually, many event logs follow the “80-20 rule”, i.e., more than 80% of all observed traces are explained by less than 20% of all the observed trace variants. Formally this means there is a set of traces X ⊆ τ (l) such that |[t ∈ l | t ∈ X]|/|l| > 0.8 and |X|/|τ (l)| < 0.2.
Because of the distribution of traces in the log, it is often too simplistic to describe a model as a set of traces. Since “behavior is not binary”, we use a trace likelihood function to describe the probability of each trace.
Definition 3 (Trace Likelihood Function). Π = T → [
When describing a trace likelihood function, we assume that the number of traces
is countable. Therefore, (Ω, F , P ) with Ω = T , F = P(T ), and P ∈ F → [
For pragmatic reasons, we can also restrict A to be finite and T to traces of a maximal length (e.g., the maximal length seen in any log). For any set of traces X ⊆ T , π(X ) = Pt∈X π(t) is the probability that a run of the process π yields a trace in X . We assume that traces are sampled independently. When considering time, this is not realistic (due to queueing), but for the control-flow (routing of a case through the model) this is a common assumption.
Definition 4 (Process Model). M is the set of process models. A process model m ∈ M has a set of traces τ (m) ⊆ T and a trace likelihood function π(m) ∈ Π .
The relation between τ (m) and π(m) is not very strict. Sometimes we will require τ (m) ⊆ {t ∈ T | π(t) > 0} (all modeled traces are possible), {t ∈ T | π(t) > 0} ⊆ τ (m) (the model allows for all traces possible), or even τ (m) = {t ∈ T | π(t) > 0}. Trace set τ (m) may be an abstraction of the real process and leave out unlikely behavior. Due to simplification, the trace set τ (m) may also allow for traces that cannot happen (e.g., particular interleavings or loops).
We define τ (m) = {t ∈ T | t 6∈ τ (m)} as the complement of the set of traces allowed by model m ∈ M (like we did for event logs).
We distinguish between representation and behavior of a model. Process model m ∈ M can be represented using a plethora of modeling languages, e.g., Petri nets, BPMN models, UML activity diagrams, automata, and process trees. Here, we abstract from the actual representation and focus on behavioral characteristics like τ (m) ⊆ T and π(m) ∈ Π .
Figure 2 shows two process models that have the same behavior: τ (m1) = τ (m2) = {ha, b, ci, ha, b, di, hb, a, ci, hb, a, di} and π12 = π(m1) = π(m2) with π12(ha, b, ci) = 0.375, π12(hb, a, ci) = 0.375, π12(ha, b, di) = 0.125, π12(hb, a, di) = 0.125, and start m4 start a b a b end end trace abc bac abcdc bacdc abcdcdc bacdcdc abcdcdcdc ...
likelihood 0.375 0.375 0.09375 0.09375 0.0234375 0.0234375 0.005859375
... (c) Likelihood of each trace trace abc bac abcdc bacdcdcdcdc frequency 4 3 2 1 π12(t) = 0 for all other traces t. The two process models m1 and m2 are not graphically annotated with probabilities. However, there are extensions of these notations to do so. We can use for example Stochastic Petri Nets (SPN) or BPMN-based simulation models. For the models in Figure 2, we assume that initially there is a “race” between a and b where both have a 50% probability to win. After both a and b occurred, c occurs with 75% probability and d occurs with 25% probability. This explains the likelihoods in Figure 2(c).
Figure 2(d) shows a possible event log l12 composed of 100 traces generated by one of these models: l12(ha, b, ci) = 44, l12(hb, a, ci) = 36, l12(ha, b, di) = 14, and l12(hb, a, di) = 6.
Process models may allow for an infinite number of traces. We use Figure 3 to illustrate this. Again both processes (m3 and m4) express the same behavior. Again there is a “race” between a and b where both have a 50% probability to win. After a and b, activity c will occur. Then there is a 75% probability that the process ends and a 25% probability that d occurs. Let ta,k = ha, bi · (hc, di)k · hci be the trace that starts with a and where d is executed k times. tb,k = hb, ai · (hc, di)k · hci is the trace that starts with b and where d is executed k times. τ (m3) = τ (m3) = Sk≥0{ta,k, tb,k}. π34 = π(m3) = π(m4) with π34(ta,k) = π34(tb,k) = 0.5 · (0.25)k · 0.75. Some example values are given in Figure 3(c).
Figure 3(d) shows a possible event log l34 composed of 10 traces generated by one of the models (m3 or m4): l34(ha, b, ci) = 4, l34(hb, a, ci) = 3, l34(ha, b, c, d, ci) = 2, and l34(hb, a, c, d, c, d, c, d, c, d, ci) = 1. Since any log contains only a finite number of traces, one can never observe all traces possible in m3 or m4. 2.3
A discovery algorithm takes an event log as input and returns a process model. For example, m1 and m2 in Figure 2 could have been discovered based on event log l = [ha, b, ci5, hb, a, di3, ha, b, di2]. Ideally, the process model captures the (dominant) behavior observed, but also generalizes without becoming too imprecise. For example, m1 and m2 allow for trace t = hb, a, ci although this was never observed. Definition 5 (Discovery Algorithm). A discovery algorithm can be described as a function disc ∈ L → M mapping event logs onto process models.
We abstract from concrete discovery algorithms. Over 100 discovery algorithms
have been proposed in literature [
As Figure 1 shows, we are interested in three types of conformance measurements. Although the focus will be on L2M (Log-to-Model) comparisons, we also briefly consider L2L (Log-to-Log) and M2M (Model-to-Model) comparisons. We start by providing precision and recall measures for L2L comparisons.
based L2L precision and recall are defined as follows: recL2LSB (l1, l2) = |τ (l1) ∩ τ (l2)| |τ (l1)| precL2LSB (l1, l2) = |τ (l1) ∩ τ (l2)| |τ (l2)|
Multiset-based L2L precision and recall are defined as follows: recL2LMSB (l1, l2) = |l1 ∩ l2| |l1| precL2LMSB (l1, l2) = |l1 ∩ l2| |l2| recL2LMSB and precL2LMSB take into account the frequencies of traces. In recL2LSB and precL2LSB it is not relevant how many times the same trace appears in the log. Consider l12 in Figure 2(d) and l34 in Figure 3(d). recL2LSB (l12, l34) = 2/4 = 0.5, precL2LSB (l12, l34) = 2/4 = 0.5, recL2LMSB (l12, l34) = (4 + 3)/100 = 0.07, and precL2LMSB (l12, l34) = (4 + 3)/10 = 0.7. This shows that the latter two measures only make sense if both logs have comparable sizes or things are normalized. (1) (2)
We also define two M2M (Model-to-Model) recall and precision measures. Definition 8 (Trace-Based M2M Precision and Recall). Let m1, m2 ∈ M be two process models. Trace-based M2M precision and recall are defined as follows: (3) (4) (5) (6)
Note that these recall and precision measures do not take into account the likelihood of traces. Moreover, they are undefined if the number of traces is unbounded, i.e., |τ (m1)| = ∞ or |τ (m2)| = ∞. These two issues can be addressed by taking into account trace likelihoods, resulting in the following measures.
Definition 9 (Likelihood-Based M2M Precision and Recall). Let m1, m2 ∈ M be two process models. Likelihood-based M2M precision and recall are defined as follows: recM2M LB (m1, m2) = precM2M LB (m1, m2) = π(m1)(τ (m1) ∩ τ (m2))
π(m1)(τ (m1))
π(m2)(τ (m1) ∩ τ (m2))
π(m2)(τ (m2))
Note that π(m1)(τ (m1) ∩ τ (m2)) quantifies the likelihood of traces in the set τ (m1) ∩
τ (m2) according to model m1 (recall that π(m1) ∈ Π = T → [
The recall and precision measures in Definition 9 seem quite natural for models and there is no need for additional notions such as generalization. However, when considering event logs, recall and precision are not addressing the fact that there is a difference between (1) the behavior in the log and (2) possible future behavior. Overfitting models may have perfect recall, but unable to allow for future cases.
In the remainder, we assume the existence of three functions: rec(), prec(), gen(). All three take a log and model as input and return a value between 0 and 1. The higher the value, the better. In process mining literature one can find many proposals for such functions. Although we provide a few example functions for clarity, we focus on desired properties of conformance measures rather than concrete measures.
fraction of observed behavior that is allowed by the model.
tify the fraction of behavior allowed by the model that was actually observed.
aims to quantify the likelihood that new unseen cases will fit the model.
If we ignore frequencies and likelihoods of traces, we can simply count fractions of traces yielding the following two simple measures.
Definition 13 (Trace-Based L2M Precision and Recall). Let l ∈ L and m ∈ M be an event log and a process model. Trace-based L2M precision and recall are defined as follows: recL2M TB (l, m) = |τ (l) ∩ τ (m)| |τ (l)| precL2M TB (l, m) = |τ (l) ∩ τ (m)| |τ (m)|
Since |τ (l)| is bounded by the size of the log, recL2M TB (l, m) is well-defined. However, precL2M TB (l, m) is undefined when τ (m) is unbounded (e.g., in case of loops).
Another approach is to build a dummy process model ml based on the event log and then apply Definition 9.
Definition 14 (Estimation-Based L2M Precision and Recall). Let l ∈ L and m ∈ M be an event log and a process model. Let ml be a model created based on l such that τ (ml) = τ (l) and π(ml)(t) = l(t)/ |l|. Estimation-based L2M precision and recall are defined as follows: genL2M q (l, m) = |[t ∈ l | t ∈ τ (m) ∧ l(t) ≥ q]|
|l| genL2M HB (l, m) = |[t ∈ l | t ∈ τ (m)]| − |τ (l) ∩ τ (m)| |l|
with q ≥ 1 recL2M EB (l, m) = precL2M EB (l, m) = π(ml)(τ (ml) ∩ τ (m)) = |[t ∈ l | t ∈ τ (m)]|
π(ml)(τ (ml)) |l| π(m)(τ (ml) ∩ τ (m)) π(m)(τ (l) ∩ τ (m))
= π(m)(τ (m)) π(m)(τ (m))
The above measures do not capture generalization. Note that generalization is good when the process model is also able to explain future traces (i.e., unseen cases). Therefore, generalization takes into account the redundancy of fitting behavior. If the log contains many fitting traces that are also frequent, then generalization is likely to be good.
Definition 15 (L2M Generalization). Let l ∈ L and m ∈ M be an event log and a process model. Two example L2M precision measures are defined as follows: (7) (8) (9) (10) (11) genL2M q (l, m) uses a threshold q. The more fitting traces there are that have a frequency of at least q, the better. Non-fitting traces or traces that are unique lower generalization. genL2M HB (l, m) measures the fraction of traces that is fitting, but subtracts a penalty for each unique trace. Consider l0 = [ha, b, ci60, hb, a, di38, ha, b, di1, hc, b, ai1] and m1 in Figure 2 and let q = 10. genL2M q (l0, m1) = (60 + 38)/100 = 0.98 and genL2M HB (l0, m1) = ((60 + 38 + 1) − 3)/100 = 0.96.
Assume now that l00 = [ha, b, ci7, hb, a, di1, ha, b, di1, hc, b, ai1]. genL2M q (l00, m1) = 0/10 = 0.0 and genL2M HB (l00, m1) = ((7 + 1 + 1) − 3)/10 = 0.6. Note that, although the set of traces in the event log did not change (τ (l0) = τ (l00)), it is reasonable to assume that generalization is impacted. 6
Many recall measures have been proposed in literature [
In the remainder, we provide 21 conformance propositions. The Merriam-Webster
dictionary defines the noun proposition as “an expression in language or signs of
something that can be believed, doubted, or denied or is either true or false” [
First, we consider a few recall propositions. rec ∈ L × M → [
Proposition RecPro1+ states that extending the model to allow for more behavior can never result in a lower recall. Similarly, it cannot be the case that adding fitting behavior to the event logs, lowers recall (RecPro2+). Adding non-fitting behavior to the log, cannot improve recall (RecPro3+).
Proposition 4 (RecPro2+). For any l1, l2, l3 ∈ L and m ∈ M such that l2 = l1 ] l3 and τ (l3) ⊆ τ (m): rec(l1, m) ≤ rec(l2, m).
Proposition 5 (RecPro3+). For any l1, l2, l3 ∈ L and m ∈ M such that l2 = l1 ] l3 and τ (l3) ⊆ τ (m): rec(l1, m) ≥ rec(l2, m).
For any natural number k: lk(t) = k · l(t), e.g., if l = [ha, bi3, hci2], then l4 = [ha, bi12, hci8]. We use this notation to enlarge event logs without changing the distribution. One could argue that this should not influence recall ( RecPro40), e.g., rec([ha, bi3, hci2], m) = rec([ha, bi12, hci8], m). However, unlike the previous propositions, this requirement is debatable as is indicated by the “ 0” tag.
Proposition 6 (RecPro40). For any l ∈ L, m ∈ rec(l, m).
M, and k ≥ 1: rec(lk, m) =
Finally, we provide a proposition stating that recall should be 1 if all traces in the log fit the model ( RecPro5+). As a result, the empty log has recall 1 for any model. Proposition 7 (RecPro5+). For any l ∈ L and m ∈ M such that τ (l) ⊆ τ (m): rec(l, m) = 1.
Based on this proposition, rec(l, discofit (l)) = rec(l, discufit (l)) = 1 for any log l. 6.3
Precision (prec ∈ L×M → [
Proposition 8 (PrecPro1+). For any l ∈ L and m1, m2 ∈ M such that τ (m1) ⊆ τ (m2) and τ (l) ∩ (τ (m2) \ τ (m1)) = ∅: prec(l, m1) ≥ prec(l, m2).
Proposition 9 (PrecPro2+). For any l1, l2, l3 ∈ L and m ∈ M such that l2 = l1 ] l3 and τ (l3) ⊆ τ (m): prec(l1, m) ≤ prec(l2, m).
Proposition 10 (PrecPro30). For any l1, l2, l3 ∈ L and m ∈ M such that l2 = l1 ] l3 and τ (l3) ⊆ τ (m): prec(l1, m) = prec(l2, m).
One could also argue that duplicating the event log should not influence precision because the distribution remains the same (PrecPro40), e.g., prec([ha, bi20, hci20], m) = prec([ha, bi40, hci40], m).
Proposition 11 (PrecPro40). For any l ∈ L, m ∈ M, and k ≥ 1: prec(lk, m) = prec(l, m).
If the model allows for the behavior observed and nothing more, precision should be maximal (PrecPro5+). One could also argue that if all modeled behavior was observed, precision should also be 1 (PrecPro60). The latter proposition is debatable, because it implies that the non-fitting behavior cannot influence perfect precision. Consider for example extreme cases where the model covers just a small fraction of all observed behavior (or even more extreme situations like τ (m) = ∅).
Proposition 12 (PrecPro5+). For any l ∈ L and m ∈ M such that τ (m) = τ (l): prec(l, m) = 1.
Proposition 13 (PrecPro60). For any l ∈ L and m ∈ M such that τ (m) ⊆ τ (l): prec(l, m) = 1.
According to PrecPro5+and PrecPro60, rec(l, discofit (l)) = 1 for any log l. 6.4
Generalization (gen ∈ L × M → [
Proposition 14 (GenPro1+). For any l ∈ L and m1, m2 ∈ M such that τ (m1) ⊆ τ (m2): gen(l, m1) ≤ gen(l, m2).
Proposition 15 (GenPro2+). For any l1, l2, l3 ∈ L and m ∈ M such that l2 = l1 ] l3 and τ (l3) ⊆ τ (m): gen(l1, m) ≤ gen(l2, m).
Proposition 16 (GenPro3+). For any l1, l2, l3 ∈ L and m ∈ M such that l2 = l1 ] l3 and τ (l3) ⊆ τ (m): gen(l1, m) ≥ gen(l2, m).
Duplicating the event log does not necessarily influence recall and precision. According to propositions RecPro40 and PrecPro40 this should have no effect on recall and precision. However, making the event log more redundant, should have an effect on generalization. For fitting logs, adding redundancy without changing the distribution can only improve generalization (GenPro4+). For non-fitting logs, adding redundancy without changing the distribution can only lower generalization (GenPro5+). Note that
and GenPro70 consider logs where some traces are fitting and others are not. For a log where more than half of the traces is fitting, duplication can only improve generalization (GenPro60). For a log where more than half of the traces is non-fitting, duplication can only lower generalization (GenPro60).
Proposition 17 (GenPro4+). For any l ∈ L, m ∈ M, and k ≥ 1 such that τ (l) ⊆ τ (m): gen(lk, m) ≥ gen(l, m).
Proposition 18 (GenPro5+). For any l ∈ L, m ∈ M, and k ≥ 1 such that τ (l) ⊆ τ (m): gen(lk, m) ≤ gen(l, m).
Proposition 19 (GenPro60). For any l ∈ L, m ∈ M, and k ≥ 1 such that most traces are fitting ( |[t ∈ l | t ∈ τ (m)]| ≥ |[t ∈ l | t 6∈ τ (m)]|): gen(lk, m) ≥ gen(l, m). Proposition 20 (GenPro70). For any l ∈ L, m ∈ M, and k ≥ 1 such that most traces are non-fitting ( |[t ∈ l | t ∈ τ (m)]| ≤ |[t ∈ l | t 6∈ τ (m)]|): gen(lk, m) ≤ gen(l, m).
When the model allows for any behavior, clearly the next case will also be tfiting (GenPro80). Nevertheless, it is marked as controversial because the proposition would also need to hold for an empty event log.
Proposition 21 (GenPro80). For any l ∈ L and m ∈ M such that τ (m) = T : gen(l, m) = 1.
This concludes this first inventory of conformance propositions. As mentioned, their
purpose is twofold. First of all, they help to understand the goals and challenges of
process discovery. Second, they provide a checklist for existing and future conformance
measures. As demonstrated in [
Although we do not aim to propose new conformance measures, we defined 6 L2M measures in Section 5. We use these example measures to discuss the usefulness of the 21 conformance propositions. Table 7 shows for each of the six conformance measure defined in Section 5 which conformance propositions always hold (marked with √). The cells tagged with × are measure-proposition combinations that can be violated.
Consider for example proposition RecPro1+ and measure recL2M EB . Obviously, |[t ∈ l | t ∈ τ (m1)]| /|l| ≤ |[t ∈ l | t ∈ τ (m2)]| /|l| if τ (m1) ⊆ τ (m2). Next, we consider PrecPro1+ and precL2M TB . |τ (l) ∩ τ (m1)| /|τ (m1)| ≤ |τ (l) ∩ τ (m2)| /|τ (m2)| if τ (m1) ⊆ τ (m2) and τ (l) ∩ (τ (m2) \ τ (m1)) = ∅ (because τ (l) ∩ τ (m2) = τ (l) ∩ τ (m1)). Similarly, we can show the correctness of all √ entries in Table 7.
More interesting are the × entries in the table. precL2M EB does not satisfy proposition PrecPro1+ because π(m1) may be very different from π(m2) even when τ (m1) = τ (m2). Both generalization measures do not satisfy GenPro2+. When adding fitting traces, these traces may be low frequent, possibly lowering both generalization measures. They also do not satisfy GenPro70. From the two definitions we can see that replication can only lead to better generalization values even when the majority of traces is not fitting. genL2M q and genL2M HB also do not satisfy GenPro80 because the proposition does not depend on the event log as long as any trace can generated by the model. The two measures do depend on the event log. Actually, genL2M HB can only approach value 1.
The × entries in the table illustrate that the properties are not as straightforward as they may seem at first glance. 8
The goal of this paper is to trigger discussion and to address common misconceptions.
When it comes to relating process models and event logs different viewpoints are
possible and often authors tend to impose their own assumptions on others without fully
understanding the different settings. Therefore, we put the definitions and propositions
presented in this paper in the context of related work. As mentioned in the introduction,
a broad range of conformance notions has been proposed in literature [
In this paper, we considered the setting where two artifacts (e.g., a process model and an event log) are given and need to be compared. We are not evaluating or comparing different discovery algorithms. Hence, one cannot use cross-validation. Cross-validation is a technique to evaluate algorithms by partitioning the original data set into a training set to discover a model, and a test set to evaluate it. In k-fold cross-validation, the original data set is randomly partitioned into k equal size subsets (cf. Figure 4). Of the k subsets, a single subset is retained as the validation data for testing the model, and the remaining k − 1 sets are used as training data. The cross-validation process is then repeated k times (the so-called folds), with each of the k subsets used exactly once as the validation data. The k results from the folds can then be combined to produce a single estimation. The whole data set is used for both training and validation and each data element is used for validation exactly once. Moreover, by comparing the performance on the different folds one gets insights into the robustness of the approach.
Cross-validation approaches can be used to evaluate process discovery algorithms. One can distribute the cases in the original event log over 10 smaller event logs. The discovery algorithm can be applied to the 10 folds and tested on the corresponding test logs. As usual, there is the problem that event logs do not provide negative examples. Therefore, recall is easier to measure than precision. Moreover, one can only use (kfold) cross-validation to evaluate an algorithm and not a process model. Therefore, it is unrelated to most of the things discussed in this paper, e.g., L2M comparison and the 21 propositions. 8.2
In this paper, we assumed that all events are recorded correctly. In [
Process variability is orthogonal to log quality. A process that exhibits many
different behaviors, some of which are frequent and others infrequent, is difficult to analyze
even when the data quality is high. See [
Given the Venn diagram showing the relationships between system S, log L, and model M , we can identify the following seven types of behavior (numbers refer to Figure 6): (1) Modeled and observed system behavior (2) Not modeled but observed non-system behavior (3) Modeled and observed non-system behavior (4) Modeled but unobserved non-system behavior (5) Modeled but unobserved system behavior (6) Not modeled and unobserved system behavior (7) Not modeled but observed system behavior
– (1) Modeled and observed system behavior (S ∩ L ∩ M ). – (2) Not modeled but observed non-system behavior (L \ (M ∪ S)). – (3) Modeled and observed non-system behavior ((L ∩ M ) \ S). – (4) Modeled but unobserved non-system behavior (M \ (S ∪ L)). – (5) Modeled but unobserved system behavior ((M ∩ S) \ L). – (6) Not modeled and unobserved system behavior (S \ (M ∪ L)).
– (7) Not modeled but observed system behavior ((S ∩ L) \ M ).
Clearly, one would like to like S and M to coincide. System-model recall can be defined as |S ∩ M | / |S| and can be maximized by minimizing (6) and (7). Precision can be defined as |S ∩ M | / |M | and can be maximized by minimizing (3) and (4). One can also define log-model recall/precision and system-log recall/precision.
Although Figure 6 is useful and consistent with the earlier definitions, it is also
too simplistic and partly misleading. First of all, in reality, we do not know the system
S. It is only possible to control and know S in an experimental setting (e.g. using a
simulation model). Second, the notion of S suggests that behavior can be classified into
system behavior and non-system behavior (i.e., a binary classification). This ignores the
likelihood of behavior and the purpose of the model (e.g., striving for the 80/20 model).
“Murphy’s Law of Process Mining” suggest that in principle anything can happen if
one is prepared to wait long enough, but it is uninteresting to return a model that allows
for any behavior. This paper clearly shows the need to include probabilities. Third,
system S may be changing over time. If we partition the timeline into segments i ∈
{1, 2, 3, . . .}, then we will be confronted with different versions of the system Si and
new events logs Li. How to relate model Mi to Si and Li while also using earlier
observations (e.g., Sj<i Lj )? Fourth, the assumption that S, L, and M are sets of traces
can be very misleading as shown in this paper. When the model has loops, |M | will
be infinite. However, |L| is always finite, making both incomparable. Fortunately, can
use other abstractions such as causal footprints [
As process mining is maturing and more commercial tools become available [
By defining 21 conformance propositions, we discussed possible requirements for conformance measures. It is surprising that seemingly obvious requirements are not met by today’s conformance measures. We used a few very simple measures to illustrate this.
The paper also stressed the need to consider probabilities. There are two main reasons for this. Likelihoods of traces in models are as natural as considering frequencies in event logs. Moreover, models with loops allow for infinitely many traces. Models with concurrency allow for a factorial number of interleavings. This shows that we cannot simply count and need a weight function to indicate the relative importance of traces.
We hope that this paper will trigger a deeper and more systematic discussion on existing and future conformance notions.