PaperlayerView exact revision on arXiv

Source-linked AI summary

Time and Activity Sequence Prediction of Business Process Instances

Mirko Polato, Alessandro Sperduti, Andrea Burattin, Massimiliano de Leoni

arXiv:1602.07566v1cs.AI

TL;DR

Predicting future properties of running business-process instances is difficult because existing approaches often assume stationary processes. This paper proposes improved and new remaining-time methods, including approaches for dynamic processes and future activity sequences, and evaluates them on two real case studies. The reported methods outperform the state of the art in the evaluated setting.

  • Problem

    Runtime prediction of remaining case time is difficult because process instances are incomplete and process behavior may be non-stationary.

  • Method

    The paper proposes three prediction methods using control-flow and additional event data, including Support Vector Regression-based approaches and activity-sequence prediction.

  • Results

    The methods are extensively evaluated on two real-life case studies and are reported to outperform state-of-the-art approaches.

  • Takeaways & Limitations

    The approach can provide remaining-time estimates together with hints about the future activity sequence of a running case.

  • Takeaways & Limitations

    The methods do not return predictions for unseen activity sequences, and future work includes parameter calibration and production-level deployment.

Abstract

from arXiv · show

The ability to know in advance the trend of running process instances, with respect to different features, such as the expected completion time, would allow business managers to timely counteract to undesired situations, in order to prevent losses. Therefore, the ability to accurately predict future features of running business process instances would be a very helpful aid when managing processes, especially under service level agreement constraints. However, making such accurate forecasts is not easy: many factors may influence the predicted features. Many approaches have been proposed to cope with this problem but all of them assume that the underling process is stationary. However, in real cases this assumption is not always true. In this work we present new methods for predicting the remaining time of running cases. In particular we propose a method, assuming process stationarity, which outperforms the state-of-the-art and two other methods which are able to make predictions even with non-stationary processes. We also describe an approach able to predict the full sequence of activities that a running case is going to take. All these methods are extensively evaluated on two real case studies.

1. Introduction

The paper addresses runtime prediction of remaining case time using event-log information beyond control flow, including settings with evolving process behavior. It proposes improved and new approaches, evaluates them on two real-life cases, and extends one model to activity-sequence prediction.

  • Runtime prediction is difficult because process instances are incomplete, individually variable, and affected by human flexibility.
  • The paper also considers transition-system, probabilistic, queue-theoretic, and decision-tree approaches for process prediction.
  • The paper targets remaining-time prediction using both control-flow information and additional event attributes.
  • The authors distinguish static workflows from dynamic processes with conditions such as seasonal drift.
  • The methods are evaluated against state-of-the-art approaches using software-company and road-traffic-fine case studies.

3. Background

This section introduces event-log data, traces, representations, and transition systems used to model process behavior. It also explains how abstraction choices affect whether the resulting system overfits or underfits the log.

  • Event logs: An event records an activity, case identifier, timestamp, and additional attributes.
  • Traces: A complete trace is a time-ordered sequence of events for one case, while a partial trace represents an unfinished running instance.
  • Event logs: An event log is a collection of traces representing recorded process executions.
  • Transition systems: A transition system consists of states, activity labels, transitions, initial states, and accepting states.
  • Transition systems: State and event representation functions map trace prefixes and events into the states and labels of a transition system.
  • Abstraction: Conservative abstractions can overfit an event log, whereas aggressive abstractions can overgeneralize it and underfit the log.

22 end

Figure 1 illustrates a transition system extracted from three trace types that share an A–B prefix and then diverge before reaching F. States encode event representations, with s0 initial and s6 accepting.

  • The transition system represents traces ⟨A, B, C, F⟩, ⟨A, B, D, F⟩, and ⟨A, B, E, F⟩.
  • The initial state is s0, and the accepting state is s6.
  • State s1{A} denotes a state whose representation is {A}, while transitions carry corresponding event-representation values.

4. Machine Learning Background

The section introduces classification and regression concepts used for prediction, including Naïve Bayes and Support Vector Regression. Naïve Bayes estimates class probabilities under a feature-independence assumption, while SVR seeks a flat function with bounded prediction deviations.

  • Classification learns a function that predicts category membership for data instances.
  • Naïve Bayes is a supervised probabilistic classifier based on Bayes’ theorem and trained from pre-classified instances.
  • Naïve Bayes assumes conditional independence, allowing the joint conditional probability to be computed as a product of feature probabilities.
  • The classifier can return the maximum a posteriori class or the probability distribution over all categories.
  • ϵ-SVR learns a function that stays within ϵ of training targets while remaining as flat as possible.
  • SVR controls flatness by minimizing the weight-vector norm, with slack variables and C governing tolerated deviations.
  • Nonlinear SVR uses feature-space mappings and kernel dot products instead of explicitly computing the higher-dimensional representation.

5. Remaining Time Prediction

Remaining-time prediction estimates how long an ongoing process instance will take to complete from historical event-log data. The proposed workflow learns from partial traces, encodes their attributes, and uses the resulting training set for machine-learning prediction.

  • Remaining-time prediction estimates the time from an ongoing process instance to completion using historical event-log traces.
  • The learned model takes a running case’s partial trace as input and returns a remaining-time forecast.
  • The paper proposes new machine-learning approaches for remaining-time prediction and discusses using one model to predict future activity sequences.
  • The prediction task is formulated as regression, with partial traces as inputs and remaining times at events as targets.
  • Event attributes are converted into numerical vectors using last observed values, one-hot encoding for nominal attributes, and direct components for numeric values.
  • The encoded attribute vectors are concatenated into fixed-order feature vectors, while rem supplies the corresponding target values.
  • Training examples are constructed from the event log and must use a consistent time granularity across instances.

12 end

The method enriches remaining-time prediction with transition-system features and similarity-based encodings for traces that do not fit the observed process model. It defines set, bag, and sequence representations and trains an ϵ-SVR using the resulting vectors.

  • Prediction: After training, the partial trace is converted into the same feature vector format and passed to the learned ϵ-SVR function to predict remaining time.The prediction is interpreted at the granularity used for the training instances.
  • Control-flow features: Transition-system features encode the control-flow path followed by a partial trace as contextual information for ϵ-SVR prediction.The transition system is selected as a trade-off between expressivity and compactness.
  • Control-flow features: States excluding the initial state are one-hot encoded as literal feature values for traces that fit the transition system.The encoding enumerates states in S \ Sstart as possible feature values.
  • Non-fitting traces: Non-fitting traces are mapped to lawful states through similarity features instead of receiving an all-zero control-flow vector.The method compares a non-fitting trace representation with states of the transition system and uses the resulting similarities in the encoding.
  • Similarity functions: Set, bag, and list abstractions use corresponding similarity functions, including Jaccard similarity for bags and Damerau-Levenshtein similarity for lists.For sequence-based similarity, event representations are converted into characters before string comparison.
  • Similarity functions: Damerau-Levenshtein distance counts the minimum insertions, deletions, substitutions, and transpositions needed to transform one string into another.The associated similarity is normalized using the maximum string length.

10 end

The data-aware transition-system approach combines control-flow structure with Naïve Bayes transition probabilities and SVR time estimates based on case attributes. It produces weighted remaining-time forecasts and can also predict likely future activity sequences.

  • An annotated transition system associates states with measurement multisets, and a prediction function aggregates those measurements into a forecast.
  • The approach enriches a transition system with Naïve Bayes classifiers on states and SVRs on transitions, trained using historical case attributes.
  • The model combines next-state probabilities with transition-specific SVR estimates to compute a weighted average over possible continuations.
  • Naïve Bayes annotations estimate the probability of reaching each next state from the current state given the case’s attribute vector.
  • The predictor transition system combines the labeled transition system with NB and SVR annotations.
  • SVR annotations estimate remaining time for a transition from the transition and the case’s attribute vector.
  • The construction procedure takes an event log and labeled transition system as input and outputs a predictor transition system.

17 end

The procedure trains an ϵ-SVR model for each transition using its corresponding training set.

  • Each transition t receives an ϵ-SVR model trained on the data in svr[t].

20 end

The procedure builds training data and models incrementally from partial traces, then predicts remaining time with a predictor transition system.

  • The first loop initializes the ϵ-SVR training sets, while the second constructs training instances and incrementally updates Naïve Bayes classifiers.Training instances use additional data from partial traces and calculated remaining time.
  • Algorithm 6 predicts a running case’s remaining time using a predictor transition system constructed by Algorithm 5.
  • The prediction combines Naïve Bayes transition probabilities with ϵ-SVR transition-time estimates, without a separate expected sojourn-time term.The expected sojourn time is implicitly embedded in the revised ϵ-SVR formulation.

12 end

The predictor transition system estimates remaining time by weighting transition-time predictions with transition probabilities and can also identify likely future activity paths.

  • Given a learned predictor transition system, prediction requires a constant number of operations bounded by the largest successor set s•.This supports application in online settings where each event triggers only a constant number of operations.
  • The system predicts the most likely complete activity sequence by finding a path from the current node to an accepting node.The example path s2{B} → s3{C} → s6{F} has probability 0.6.
  • Sequence likelihoods multiply transition probabilities, so the method transforms probabilities into additive graph costs using the negative logarithm.Low-probability transitions receive high costs, while probabilities near 1 receive costs near zero.

6. Implementation

The methods are implemented as ProM plugins using Weka’s Naïve Bayes and Support Vector Regression implementations, with an online querying interface for predictions.

  • 6. Implementation: The implementation uses ProM for transition-system mining and Weka for Naïve Bayes classification and Support Vector Regression.SVR uses Weka’s SMO implementation.
  • 6. Implementation: A ProM plugin builds prediction models, while another exposes an online JSON-based service that other information systems can query.
  • 6. Implementation: Negligible forecast computation time supports adoption in intensive online scenarios.

7. Results

The experiments evaluate remaining-time and activity-sequence prediction on two real-world process logs, comparing baseline, data-aware, regression, and transition-system approaches. Results show broad improvements over the baseline, with similarity-based SVR+TS strongest on unseen or changing behavior and strong sequence-prediction accuracy.

  • Experimental setup: Two real-world case studies evaluate the proposed methods using 5-fold cross validation: road-fines management and help-desk ticketing.The road-fines log contains about 7,300 traces; the help-desk log has almost 4,500 instances and over 21,000 events.
  • Case Study 1: Road Fines Log: Every proposed approach outperforms the baseline on the road-fines log, with DATS best on RMSPE and SVR+TS best on MAPE.The authors attribute the improvement mainly to adding data beyond control-flow information.
  • Case Study 2: Help Desk Log: 14% lower MAPE and 4% lower RMSPE are achieved on average for the help-desk log relative to the baseline.DATS using the set abstraction achieves the lowest MAPE and RMSPE; SVR+TS and DATS outperform simple SVR, highlighting the value of transition-system information.
  • Unseen process variants: SVR+TS outperforms all other approaches on process variants excluded from training, with MAPE around 34% and RMSPE of 55%.Its similarity mechanism uses correlated states when the correct state is unavailable, making predictions less sensitive to noise or workflow change.
  • Future Sequence of Activities Prediction: FPP identifies the next activity almost 94% of the time, while the next-two-activity similarity averages almost 0.86 with a 71% hit rate.For DAM and PRE, the proposed approach averages 0.81 and 0.63, compared with 0.36 and 0.09 for the random method.
  • Future Sequence of Activities Prediction: Prediction-accuracy differences are clearest for near-future activities and narrow farther ahead as uncertainty accumulates across future steps.The accumulated uncertainty makes FPP increasingly close to the random method for more distant predictions.

8. Conclusions

The paper proposes three prediction methods that use control-flow and event-log data, address stable and dynamic processes, and handle unexpected behavior. Evaluations on real-life data show improvements over state-of-the-art approaches, with different methods suited to different process scenarios.

  • The paper proposes three prediction methods using both control-flow information and additional event-log data.
  • The approaches use machine-learning techniques to incorporate additional information into prediction models.
  • Similarity with previously observed process flows helps the methods handle unexpected behavior and noisy data.
  • The algorithms were extensively evaluated on real-life data and outperformed state-of-the-art approaches.
  • The methods address stable processes containing all possible behaviors and dynamic processes with drifts or unseen behaviors.
  • For stable processes, DATS overcomes the state of the art, while similarity-based SVR performs well when training data omit process behaviors.
  • Future work includes improving parameter calibration, evaluating work-hours-only prediction, and testing the approach under production-level constraints.
Loading 1602.07566v1…