In declarative Process Mining (PM), accounting for uncertainty is essential to accurately model realworld business processes. Up to now, most traditional approaches have overlooked the possibility of integrating probability into process management. Starting from our previous works on this topic, we present an extension to our semantics that underlies a probabilistic declarative framework for PM, in such a way that we can manage uncertainty at multiple levels, from individual events to entire logs, by assigning probabilities reflecting a degree of belief or confidence in them. This framework is based on the Distribution Semantics of Probabilistic Logic Programming.
Ongoing research in Process Mining (PM) is increasingly focusing on the role of uncertainty
in business process management. Uncertainty in PM can manifest in multiple aspects of a
process, ranging from process models to process data, i.e. events and event attributes, traces,
and logs. For instance, real-world event logs may contain incomplete or noisy data, where
some events/traces are missing or misrecorded. Various approaches have been explored to
address uncertainty in procedural PM settings, dealing with structured, sequential process
models, typically represented as flow-based notations like Petri nets or BPMN diagrams. In
recent years, significant research built on foundational work by Pegoraro and Van der Aalst has
been devoted to address this challenge with respect to event data [
However, a distinct approach can be taken when dealing with uncertainty in declarative PM,
which focuses only on the constraints between activity sequences, rather than outlining exact
workflows [
Starting from our previous work based on probabilistic declarative process specifications [
In [
PLP, notably through the Distribution Semantics, handles uncertain information by allowing
probabilities in logic programs, which define probability distributions over a set of possible
normal logic programs called "worlds" . In the following, the DS will be described with reference
to the language of LPADs (Logic Programs with Annotated Disjunctions) [
An annotated disjunctive clause is of the form ℎ1 : 1; . . . ; ℎ : : − 1, . . . , ,
where ℎ1, . . . , ℎ are logical atoms and {1, . . . , } are real numbers in the interval [
An atomic choice [
We denote the set of all worlds of by . ( ) is a probability distribution over worlds, i.e., ∑︀∈ () = 1. A composite choice identifies a set of worlds = { | ∈ , ⊇ }. The set of possible worlds associated to a set of composite choices is = ⋃︀ ∈ . Example 1. Consider the following LPAD T encoding the outcome of tossing a coin, which may be either fair or biased: (1) (2) (3) (4) ℎ() : 0.5; () : 0.5 : − (), \+(). ℎ() : 0.6; () : 0.4 : − (), (). () : 0.9; () : 0.1.
().
If a coin is tossed, the probability of it landing heads or tails is influenced by whether it is fair or biased: if the coin is fair ( \+biased), then it has an equal chance of landing heads or tails (0.5). If the coin is biased, then it is more likely to land heads with a probability of 0.6, and tails with a probability of 0.4. 3 states that the coin is fair with a probability of 0.9 or biased with a probability of 0.1. 4 asserts that a coin is indeed tossed. Since we’re only considering 1 coin, each rule has 1 grounding 1 = {/}. Here, would have 2 × 2 × 2 = 8 possible worlds.
Given a goal G, its probability () can be defined by marginalizing the joint probability of the goal and the worlds: () = ∑︀∈ (, ) = ∑︀∈ (|) () = ∑︀∈ :|= (). The probability of a goal given a world is (|) = 1 if |= and 0 otherwise. () = ( ), i.e. is the product of the annotations of the head atoms selected in . Therefore, the probability of G can be computed by summing the probability of the worlds where the goal is true. In practice, given a goal to solve, it is unfeasible to enumerate all the worlds where is entailed. Inference algorithms, instead, find explanations for a goal: a composite choice is an explanation for if is entailed by every world of . Example 2. (Ex.1 cont.) To determine the overall probabilities of the coin landing on heads or tails, we need to ask the probability of the 2 goals heads and tails. Each goal is true in 4 worlds out of the 8:
(heads) = (0.5 × 0.6 × 0.9) + (0.5 × 0.6 × 0.1) + (0.5 × 0.4 × 0.9) + (0.5 × 0.6 × 0.1) = 0.51 (tails) = 1− (heads) = (0.5× 0.4× 0.1)+(0.5× 0.6× 0.9)+(0.5× 0.4× 0.1)+(0.5× 0.4× 0.9) = 0.49
In this Section, we present our semantic framework for addressing uncertainty across events,
traces, and logs, building upon the DS. This approach acknowledges that in certain domains,
complete observation of a process instance may not be feasible, leading to uncertainty related to
events, traces and even logs. We can assign a probability to events [
With a finite alphabet of symbols Σ, representing activity names or descriptors, we can
define:
Definition 1 (Trace and Log). A Trace is a finite, ordered sequence of symbols over Σ, denoted as
∈ Σ* , where Σ* represents the infinite set of all possible finite sequences (sentences) . Syntactically,
a trace is expressed as = ⟨e1, e2, . . . , e⟩, e ∈ Σ, where is the length of the trace, and e (for
∈ 1 . . . ) represents the -th event in the trace. A log ℒ consists of a finite set of such traces.
Definition 2 (Probabilistic Event [
For example, the probabilistic event 0.8:early_mobilization in a trace of a medical log describes
the event of a patient’s early mobilization after surgery with probability 0.8, reflecting our
degree of belief associated with the event’s occurrence. In [
Now we extend our framework to probabilistic logs, driven by real-world scenarios where traces may not be accurately captured due to factors like software or hardware malfunctions and human error. As a consequence, there is no certainty of the happening of some process instance. However, due to the domain’s characteristics, it may be the case that the whole instance (trace) happened with a certain probability.
Definition 3 (Probabilistic Log). A probabilistic log ℒ is a log where at least one trace is annotated with a probability . A probability value of 1 means the trace certainly happened and the value will be omitted.
Instead of considering the happening of the single events in a trace, as in Def. 2, here we are inquiring about the certainty of the process instance as a whole: it certainly happened or maybe it happened with a degree of confidence.
Example 3. In hospitals, patients are first admitted to the emergency department following an initial screening known as triage. In exceptional situations, such as during serious emergencies, the triage process might be performed but not recorded in the log. The probabilistic log: ℒ = { 1, 0.9 : 2, 3, 0.7 : 4 } describes a scenario in which the process instances 1 and 3 were observed and recorded, while 2 was not observed but there is a high probability (0.9) that it happened. Similarly, 4 was not observed but there is a fair probability (0.7) that it happened.
We propose a straightforward extension of Sato’s distribution semantics, as done in [
Definition 4 (Selection over a probabilistic log ℒ). A Selection (ℒ) is defined as a composite choice containing an atomic choice (t, ) for each trace ∈ ℒ. A selection (ℒ) identifies a world in this way: = {|(, 1) ∈ }.
Example 4. Given the probabilistic log ℒ described in Example 3, four selections are possible, generating four corresponding worlds: 1(ℒ) = { (2, 1), (4, 1)}
1 (ℒ) = { 1, 2, 3, 4 } 2(ℒ) = { 3(ℒ) = { 4(ℒ) = { (2, 1), (2, 0), (2, 0), (4, 0)} (4, 1)} (4, 0)} 2 (ℒ) = { 1, 2, 3 3 (ℒ) = { 1, 3, 4 4 (ℒ) = { 1, 3 } } }
Note that traces 1 and 3 always appear in the generated worlds as they are certain. A possible world (ℒ) represents a possible log, determined by the presence or absence of individual uncertain traces. A selection over such a log determines which traces are considered to be part of a possible realization of the log.
Definition 5 (Probability of a Selection (ℒ)). The probability of a selection (ℒ) over a probabilistic log ℒ is defined as: ( (ℒ)) = ∏︁
∏︁ (,1)∈ (ℒ) (,0)∈ (ℒ) (1 − ) The probability of a selection corresponds to the probability of a possible log (i.e., a possible world), obtained by multiplying the probabilities associated to each alternative (presence or absence of a trace) as these are considered independent of each other. This gives a probability distribution over the logs, i.e. ∑︀ ( (ℒ)) = ( (ℒ)) = 1.
Example 5 (Ex. 4 cont.). The probabilities of the four selections (ℒ) are: ( 1(ℒ)) = ( 1(ℒ)) = 0.9 × 0.7 = 0.63 ( 2(ℒ)) = ( 2(ℒ)) = 0.9 × 0.3 = 0.27 ( 3(ℒ)) = ( 3(ℒ)) = 0.1 × 0.7 = 0.07 ( 4(ℒ)) = ( 4(ℒ)) = 0.1 × 0.3 = 0.03 Note that 0.63+0.27+0.07+0.03=1. The 4 realizations of the log, with very diferent probabilities in this case, highlight the fact the very high (low) values of confidence in the happening of some traces may generate logs with much higher (lower) confidence than others. This means that a user can rank the probabilistic realizations of the logs from the one with highest confidence (the most probable) to the one with the lowest confidence.
In this work, we presented a unified framework inspired by the distribution semantics of Probabilistic Logic Programming, which integrates our recently proposed probabilistic semantics for process events to handle uncertainty at various granularity levels: not only events, but also traces and logs. In the future, we plan to extend this framework to include proof procedures for conformance checking for probabilistic logs.
Research funded by the Italian Ministerial grant PRIN 2022 “Probabilistic Declarative Process Mining (PRODE)”, n. 20224C9HXA - CUP F53D23004240006, funded by European Union – Next Generation EU. Research funded by the Italian Ministry of University and Research through PNRR - M4C2 - Investimento 1.3 (Decreto Direttoriale MUR n. 341 del 15/03/2022), Partenariato Esteso PE00000013 - "FAIR - Future Artificial Intelligence Research" - Spoke 8 "Pervasive AI" - CUP J33C22002830006, funded by the European Union under the NextGeneration EU programme".