Process mining extracts event logs from information systems to derive insights into organizational business processes. Stochastic process mining specifically emphasizes techniques that integrate the frequency and probability of various process behaviors, allowing organizations to comprehend their business processes by diferentiating between routine and exceptional occurrences. The ambition of my Ph.D. project is to improve state-of-the-art stochastic process discovery techniques and provide novel measures applicable to stochastic conformance checking.
This section serves to motivate and formalize the research questions for my Ph.D. project.
Two types of stochastic process modeling formalism have been proposed for stochastic process modeling:
action graph-based models and Petri net-based models. The first type is the stochastic action graph
introduced by Alkhammash et al. [
CEUR
ceur-ws.org
EvEevnetnt lolgog
StSetpep1 1 CoCnotnrtorlo-fll-oflwow mmodoedlel
StSetpep22
StSotcohcahsatsitcic mmododelel
EEvveenntt SStetepp11 lologg
SStotocchhaasstitcic
mmooddeel l
and “can follow” dependencies inferred from the event log. The second type consists of Petri nets
with stochastic extensions. For instance, Leemans et al. [
Although these formalisms have been studied thoroughly, other process modeling languages, such as Business Process Model and Notation (BPMN) and causal nets, can also be extended with the stochastic perspective. In practice, BPMN is a set of diagramming conventions used to describe business processes. Causal nets are a declarative process modeling formalism that relies on a small number of modeling constructs, but is expressive. Consequently, the first research question (RQ1) is formalized as: What is the appropriate modeling formalism to model the stochastic perspective of the process? Proposed solution Business Process Model and Notation (BPMN) models are widely used by practitioners for decision making. Causal nets (C-nets) are used in multiple process discovery techniques. Many Markov models, such as Markov chains, Markov decision processes, or semi-Markov decision processes, have diferent characteristics. Similarly, transition systems have also been enhanced with probabilistic information and have been used for prediction. We propose a comparison study to justify the benefits of the selected stochastic process models compared to other stochastic process modeling languages.
Although conventional process discovery methods excel in many areas, they have the limitation of ignoring the frequencies of the traces recorded in the event logs in the constructed models. Stochastic process discovery techniques mine models that pair traces with indications on how likely one can expect to see them in future executions of the process. Most techniques achieve this through an indirect method, which involves a conventional process discovery technique to construct the process flow and then add probability weights based on how often each trace appears, as illustrated in Fig. 1.
The technique in [
At the start of my Ph.D., the second research question (RQ2) was formalized as: Given an event log and a process model that describes the control flow of the process observed in the event log, how do we construct a stochastic process model that maintains the same control flow while being capable of reproducing the probability of the observed process? Proposed solution We propose to define two-stage stochastic process discovery as finding a model with an optimal stochastic conformance checking measure over a given representation bias. Our strategy is to turn the given control flow model into a stochastic process model that assigns a weight parameter to every transition. Then, stochastic discovery is posed as an optimization problem, where values for the weights must be found so that a stochastic conformance measure is maximized.
The one-stage techniques operate without relying on an initial control-flow model, but calculate
controllfow and stochastic aspects simultaneously, as illustrated in Fig. 2. Toothpaste Miner [
IT system stochastic model record discover
event log discover
event log
single-stage technique, which applies a set of reduction and abstraction rules to generate a stochastic
labeled Petri net (SLPN). Another technique GASPD is based on grammatical inference [
However, these two one-stage approaches do not guarantee the stochastic quality of the constructed models. Thus, our third research question (RQ3) is: Given an event log, how to directly construct a stochastic process model of manageable size while capable of reproducing the probability of the observed process in the event log? Proposed solution We plan to address inherently competing objectives: Reducing the complexity of the model while maintaining its stochastic quality. Thus, the one-stage discovery is addressed through a trade-of between model complexity and accuracy.
Another core problem studied in process mining is conformance checking, which quantifies how much a process model agrees with an event log. The technique that ignores the stochastic perspective of processes can be misleading. For instance, non-stochastic-aware conformance checking cannot distinguish the discrepancy between event log [⟨, ⟩ 50, ⟨, ⟩ 50] and a stochastic process model that describes the stochastic language [⟨, ⟩ 0.9, ⟨, ⟩ 0.1]. However, the model emphasizes that step should occur after more frequently than after , while the log suggests that both orders are equally likely.
Beyond regular Log-to-Model (L2M) scenarios, Model-to-Model (M2M) and Log-to-Log (L2L) conformance checking also benefit from a stochastic perspective. In many real-life scenarios, processes are influenced by internal or external requirements and change over time. Consequently, a stochastic process model designed to describe the behavior of the system can become outdated as time progresses. One can detect and quantify changes in stochastic behavior by comparing the latest discovered model with the original model using M2M stochastic conformance. Similarly, event logs that cover long periods or merge data from multiple organizations may contain diferent versions of the process behavior. Conclusions drawn from such logs may be misleading or biased when addressing specific regional or temporal issues. We illustrate these scenarios of stochastic conformance checking in Fig. 3.
In light of this, we establish our fourth research question (RQ4) as: How to quantify stochastic conformance checking for log-to-log, log-to-model, and model-to-model conformance scenarios? Proposed solution In essence, an event log can be considered as a finite sample drawn from a probability distribution over traces, while stochastic process models represent probability distributions over traces. We propose adapting established statistical distances between probability distributions for stochastic conformance checking. Specifically, we review interesting features of statistical distances and discuss their use in the context of L2L, L2M, and M2M conformance checking. To expand the applicability of the distances, we propose the necessary adaptations.
Although existing techniques [
Conformance checking techniques, such as alignments, identify a path allowed by the model with as few deviations as possible from an observed trace. However, when considering a stochastic perspective, if the selected path is unlikely according to the stochastic process model, it may not be the most likely explanation of the path through the model. As a consequence, further diagnostics are based on process behavior that is less relevant to be followed by design. For instance, a path with a probability of 10% according to the model and an edit distance of 3 to the trace may be a better match than a path with a probability of 0.1% and an edit distance of 2. The scenario highlights two possibly competing objectives when matching the trace to the stochastic model of the process: the probability of the selected path allowed by the model and its edit distance to the trace.
Therefore, we formalize our fith research question (RQ5) as: Given an observed trace, how to match it to a stochastic process model by identifying a likely model path with a low edit distance to the trace? Proposed solution The trade-of between the probability of the selected path allowed by the model and its edit distance to the trace, which we illustrate in Fig. 4. The Pareto front consists of model paths and indicates that any reduction in edit distance would necessarily decrease the model path probability, and any increase in model path probability would necessarily increase its edit distance to the trace. We propose a stochastic alignment technique that matches a single trace to a stochastic process model and produces an alignment that balances the importance of the normative behavior (the probability of the model path) and the alignment cost (the edit distance between the model path and trace). Business analysts can explicitly weigh the trade-of with a user-defined parameter.
• Literature review to identify research gaps for stochastic process mining. • Study 1: Define and implement the two-stage discovery problem with an optimality guarantee.
The results of this study were published in CAiSE 2024 [
To complete the Ph.D. project and thesis, my future research plan is as follows: • Study 4: Identify alternative process modeling formalisms other than SLPNs to model the stochastic perspective of the process. • Study 5: Design a one-stage stochastic process discovery technique, and conduct an extensive evaluation.
Studies 4 and 5 are based on the existing work achieved in studies 1, 2, and 3. The quality of the discovered stochastic process models can be evaluated with the stochastic conformance checking measures discussed in the study.
However, two challenges may prevent the project from achieving our target. First, the stochastic discovery that guarantees stochastic optimality requires solving a nonconvex optimization problem. This poses a computational challenge as there are multiple locally optimal points, and the computed result may not be globally optimal. Second, the model-to-model stochastic conformance can be hard to measure because of potentially infinite process behavior. The conformance between two stochastic models can be computed by sampling, however, this does not guarantee an exact result.
This Ph.D. project will contribute to the business process management (BPM) community by developing novel techniques for stochastic process mining. We treat the probability of process behavior as a ifrst-class citizen due to its close link to simulation, prediction, and recommendation.
We aim to consider the appropriate representation bias for stochastic process modeling. Then, we plan to explore two types of stochastic discovery algorithms, i.e., a one-stage approach that directly constructs a stochastic model from the input event log and a two-stage approach that indirectly constructs a stochastic model using the event log. Furthermore, two types of stochastic conformance checking are investigated, one is the statistical distance-based techniques that measure numerically; the other is an alignment technique that returns an explicit artifact to match a trace with the given stochastic process model.
Simultaneously, to bridge the theory-practice divide, we will create user stories that tie all our research questions together and demonstrate the practical application of our findings in real-world scenarios. The goal is to illustrate how practitioners can leverage our research to address real-life challenges. For example, we will showcase how practitioners can perform stochastic alignments to explain deviations in an observed trace using the discovered stochastic process models.