Introduction

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 [1]. This has been achieved through a framework designed to represent the control-flow dimension of uncertain events as Petri nets, involving stochastic process modeling techniques like stochastic Petri nets [2], behavioral nets [3,4], and trace alignment [5,6]. This research highlighted the complexities of managing uncertain event data within procedural models, focusing on strong uncertainty (unknown probability distributions for attribute values) at the attribute level of events.

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 [7,8]. For example, [9] introduced the notion of probabilistic process constraints, by associating probabilities to Declare constraints.

Starting from our previous work based on probabilistic declarative process specifications [10] and probabilistic events [11], here we extend the underlying semantics in order to comprehensively handle uncertainty at all levels of process data, from traces to entire logs. This semantics is inspired by the Distribution Semantics (DS) [12] of Probabilistic Logic Programming (PLP) and handles uncertainty by expressing probabilities as a degree of belief (taking inspiration from [13], [14]) in traces and logs.

In [11], we treat uncertain events in a process trace by annotating them with a probability expressing the user's confidence in that event(s) happening. Here, we complete this framework by considering probabilities attached to traces as a whole, which results in probabilistic logs. For instance, there might be cases where a maintenance task, composed of different phases (the trace's events), is not logged correctly due to human error or system issues. If a technician recalls performing it but later finds no documentation of this in the system, he might estimate, based on his memory, interactions with colleagues, and standard operating procedures, that there is a 95% probability the inspection was completed as required. This would generate two possible logs, one with the trace included, with 0.95 probability, and the other log without the trace, but much less probable (0.05 probability). To the best of our knowledge, previous efforts in procedural PM have addressed either event-based or traced-based uncertainty separately, while our approach is new in handling probabilities from events to logs, offering an integrated semantics to manage and interpret uncertainty in process data at all levels of granularity.

Background: Distribution Semantics

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) [15], even if it underlies many other languages. A detailed survey of the DS in PLP can be found in [16]. In LPADs each program clause has a disjunction in the head with each atom annotated by a probability. When the clause body holds true, only one head atom is selected together with its probability.

An annotated disjunctive clause 𝐶 𝑖 is of the form ℎ 𝑖1 : 𝑝 𝑖1 ; . . . ; ℎ 𝑖𝑛 𝑖 : 𝑝 𝑖𝑛 𝑖 : − 𝑏 𝑖1 , . . . , 𝑏 𝑖𝑚 𝑖 , where ℎ 𝑖1 , . . . , ℎ 𝑖𝑛 𝑖 are logical atoms and {𝑝 𝑖1 , . . . , 𝑝 𝑖𝑛 𝑖 } are real numbers in the interval [0, 1] such that

∑︀ 𝑛 𝑖 𝑘=1 𝑝 𝑖𝑘 ≤ 1; 𝑏 𝑖1 , . . . , 𝑏 𝑖𝑚 𝑖 is indicated with 𝑏𝑜𝑑𝑦(𝐶 𝑖 ). If ∑︀ 𝑛 𝑖 𝑘=1 𝑝 𝑖𝑘 < 1,

the head implicitly contains an extra atom 𝑛𝑢𝑙𝑙 that does not appear in the body of any clause and whose annotation is 1 − ∑︀ 𝑛 𝑖 𝑘=1 𝑝 𝑖𝑘 . We denote by 𝑔𝑟𝑜𝑢𝑛𝑑(𝑇 ) the grounding of an LPAD 𝑇 . An atomic choice [17] is a triple (𝐶 𝑖 , 𝜃 𝑗 , 𝑘) where 𝐶 𝑖 ∈ 𝑇 , 𝜃 𝑗 is a substitution that grounds 𝐶 𝑖 and 𝑘 ∈ {1, . . . , 𝑛 𝑖 } identifies one of the head atoms. (𝐶 𝑖 , 𝜃 𝑗 , 𝑘) means that, for the ground clause 𝐶 𝑖 𝜃 𝑗 , the head ℎ 𝑖𝑘 was chosen. A set of atomic choices 𝜅 is consistent if only one head is selected from the same ground clause; we assume independence between the different choices. A composite choice 𝜅 is a consistent set of atomic choices [17]. The probability 𝑃 (𝜅) of a composite choice 𝜅 is the product of the probabilities of the independent atomic choices, i.e. 𝑃 (𝜅) = ∏︀ ( 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

Probabilistic events, traces and logs

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 [11], obtaining probabilistic traces, or to traces as a whole, obtaining probabilistic logs. Probability always reflects the degree of belief or confidence of the user in the happening of the event or the trace.

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 𝑡 = ⟨e 1 , e 2 , . . . , 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 [11]). A Probabilistic Event is a couple Prob:EventDescription, where EventDescription is a symbol describing an event (EventDescription ∈ Σ), while Prob ∈ [0, 1] is the probability that the event happened. A probability value of 1 means the event happened, and we will refer to it as "certain".

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 [11], we defined a trace where at least one event is probabilistic as a probabilistic trace. 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 [11], to the case of probabilistic logs.

𝜎 1 (ℒ 𝑝 ) = { (𝑡 2 , 1), (𝑡 4 , 1)} 𝑤 𝜎1 (ℒ 𝑝 ) = { 𝑡 1 , 𝑡 2 , 𝑡 3 , 𝑡 4 } 𝜎 2 (ℒ 𝑝 ) = { (𝑡 2 , 1), (𝑡 4 , 0)} 𝑤 𝜎2 (ℒ 𝑝 ) = { 𝑡 1 , 𝑡 2 , 𝑡 3 } 𝜎 3 (ℒ 𝑝 ) = { (𝑡 2 , 0), (𝑡 4 , 1)} 𝑤 𝜎3 (ℒ 𝑝 ) = { 𝑡 1 , 𝑡 3 , 𝑡 4 } 𝜎 4 (ℒ 𝑝 ) = { (𝑡 2 , 0), (𝑡 4 , 0)} 𝑤 𝜎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 𝑃 (𝜎 3 (ℒ 𝑝 )) = 𝑃 (𝑤 𝜎3 (ℒ 𝑝 )) = 0.1 × 0.7 = 0.07 𝑃 (𝜎 2 (ℒ 𝑝 )) = 𝑃 (𝑤 𝜎2 (ℒ 𝑝 )) = 0.9 × 0.3 = 0.27 𝑃 (𝜎 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 different 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.

Conclusions and Future Work

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.