Process Mining in Stochastic Settings

Abstract: Alignment-based conformance checking constructs optimal correspondences between observed process executions and normative models, enabling precise identification of deviations for root-cause analysis and process improvement. However, two fundamental challenges limit its applicability in modern settings: exponential state-space growth, which renders exact methods infeasible for very long traces, and uncertainty introduced when activity labels are inferred from sensors or machine learning classifiers rather than directly observed. This thesis addresses both challenges through three contributions unified by the alignment framework. First, we introduce SKTR (Stochastically Known Trace Recovery), an algorithm that recovers deterministic traces from probabilistic event logs by formulating trace recovery as alignment over a stochastic synchronous product multigraph. SKTR balances fidelity to probabilistic observations with structural validity through configurable cost functions, achieving accuracy improvements exceeding 10% over argmax baselines across five datasets. Second, we present DICE (Dynamic Window, Memory-Enhanced Conformance Checking), a framework for scaling alignment computation to very long traces. DICE partitions traces into windows that are aligned independently while propagating process state across boundaries. Adaptive boundary merging, memorization of recurring patterns, and forward-looking cost estimation maintain near-optimal alignment quality while reducing runtime by factors of 3 to 15 compared to exact methods. Third, we bridge process mining and computer vision by reformulating temporal action segmentation as a stochastic alignment problem. Our window-based decoding framework integrates neural network predictions with Petri net constraints and learned transition statistics, achieving competitive performance on standard benchmarks while requiring approximately an order of magnitude less training data than grammar-based alternatives. Together, these contributions extend alignment-based conformance checking to settings previously considered intractable, demonstrating the versatility of process mining formalisms for sequential prediction problems beyond traditional business process domains.