TL;DR
This paper introduces "stochastic process trees" (SPTs) as a more direct and less ambiguous way to model the probabilistic behavior of business processes compared to traditional stochastic Petri nets. By adding probabilities directly to process tree operators, SPTs reduce the number of parameters and clarify their role, simplifying the process of discovering and optimizing stochastic models from event logs.
What Problem Does This Paper Address?
Process mining aims to discover models that represent the behavior of business processes from event logs. A key challenge is capturing not just the sequence of activities but also their likelihood or frequency. The traditional approach involves first discovering a non-stochastic model (like a process tree or Petri net) and then adding stochasticity by assigning weights to transitions. However, this indirect approach has drawbacks:
- Ambiguous parameter roles: In Petri nets, weights assigned to transitions can have unclear or multiple impacts on the overall probability of a process trace, making it hard to understand their influence.
- Redundant parameters: Different Petri nets can represent the same process tree, leading to a non-unique and potentially inflated number of parameters to optimize. This complexity makes finding optimal stochastic models more difficult.
The paper addresses these issues by proposing a more direct method for stochastic process discovery.
Methods
The core contribution is the introduction of stochastic process trees (SPTs). This formalism extends standard process trees by incorporating probabilistic parameters directly into the operators.
- Process Trees (PTs): These are hierarchical models using operators like sequence (→), choice (×), parallel (∧), and loop (↺) to represent process structures.
- Stochastic Process Trees (SPTs): SPTs enhance PTs by associating probabilities with choice, parallel, and loop operators. For instance, a choice operator might have probabilities assigned to each branch, indicating the likelihood of taking that path. A parallel operator uses probabilities to guide the interleaving of traces from different sub-processes. A loop operator uses a probability to determine how many times a sub-process is repeated.
- Direct Stochasticity: Instead of converting a PT to a Petri net and then adding weights, SPTs allow stochasticity to be defined directly on the PT structure. This means the probability parameters are local to the operator they are associated with, making their role clear and reducing the overall number of parameters.
- Simulation and Approximation: The paper provides procedures for simulating traces from an SPT and for approximating its stochastic language.
Datasets
The paper uses three versions of a real-world event log from the Business Process Intelligence Challenge (BPIC) 2013: BPIC13_c (closed), BPIC13_i (incidents), and BPIC13_o (open). These logs represent executions of an incident management system.
Key Insights and Ideas
- Parameter Clarity: Assigning probabilities directly to SPT operators makes their role in determining trace probabilities explicit and local, unlike the often ambiguous weights in stochastic Petri nets.
- Reduced Dimensionality: SPTs require significantly fewer parameters than equivalent Petri net models derived from process trees, simplifying the optimization process.
- Avoiding Ambiguity: By bypassing the conversion to Petri nets, SPTs avoid the issue of multiple, semantically equivalent Petri nets representing the same process tree, thus ensuring a well-defined parameter space.
- Direct Modeling: The approach allows for stochastic process discovery to operate directly on process trees, streamlining the discovery pipeline.
Key Results
The paper presents preliminary experimental results using the BPIC13 event logs.
- Parameter Reduction: For the tested logs, SPT models required roughly half the number of parameters compared to their corresponding Petri net models derived from process trees. For example, BPIC13_c had 10 parameters for the SPT versus 20 for the WN.
- Competitive Performance: The optimized SPT models achieved comparable or better results in terms of restricted Earth Mover's Distance (rEMD) compared to previous work using PT-based Petri net models. For instance, final rEMD values for the logs were 0.04, 0.18, and 0.07.
- Efficiency Potential: While the current implementation is a preliminary simulation-based prototype, the authors anticipate that developing efficient computational algorithms for SPT analysis will significantly improve performance and reduce execution time.
Limitations and Future Work
- Simulation-Based Approximation: The current implementation relies on simulation to approximate the stochastic language of SPTs. This can be computationally intensive and may not always find the globally optimal parameters.
- Computational Algorithms: The authors plan to develop efficient computational algorithms for calculating SPT languages, moving beyond simulation for better accuracy and speed.
- Broader Experiments: Further experiments with a wider range of real-world event logs are planned to demonstrate the approach's validity and robustness.
- Other Distributions: The loop operator currently uses a geometric distribution for the number of executions. The authors note that this can be extended to other distributions if needed.
- Disjoint Alphabets: The paper mentions that for SPTs with disjoint alphabets, summations in operator semantics can be simplified, but this is left for future work.
Summary updated