Proactive Process Adaptation Using Deep Learning Ensembles

Problem. As mentioned above, one key requirement for proactive process adaptation are accurate predictions. Informally, prediction accuracy characterizes the ability of a prediction technique to forecast as many true violations as possible, while generating as few false alarms as possible [33]. Prediction accuracy is important for two main reasons [21]. First, accurate predictions deliver more true violations and thus trigger more required adaptations. Each missed required adaptation means one less opportunity for preventing or mitigating a problem. Second, accurate predictions mean less false alarms, and thus triggering less unnecessary adaptations. Unnecessary adaptations incur additional costs for executing the adaptations, while not addressing actual problems.

Previous research on predictive process monitoring (see [16] for an overview) focused on aggregate accuracy, such as precision or recall. Even though a high aggregate accuracy is beneficial, it does not provide direct information about the accuracy of an individual prediction. Knowing the accuracy of an individual prediction is important, because some predictions may have a higher probability of being correct than others. Proactive adaptation decisions are taken on a case by case basis. Therefore, the information about whether an individual prediction may be correct provides additional support for decision making [18, 19].

Prediction techniques traditionally used for predictive process monitoring (such as decision trees, k-nearest-neighbors, support vector machines, and multi-layer perceptrons [8, 16]) can provide probabilities to indicate whether an individual prediction is correct (e.g., in the form of class probabilities of a decision tree). Yet, probabilities estimated by most of these prediction techniques are poor [38]. In contrast, so called reliability estimates (e.g., computed from ensembles of prediction models) can provide better estimates of the probability that an individual prediction is correct [2].

Related Work. To improve aggregate prediction accuracy, deep learning techniques are being employed for predictive process monitoring [5, 9, 17, 26, 27, 34]. In particular, Recurrent Neural Networks (RNNs) are employed, which are a special type of artificial neural network, where each neuron also feeds back information into itself [5, 10]. Empirical evidence indicates that RNNs provide significant accuracy improvements for predictive process monitoring [5, 20, 34]. As an example, the empirical results of our previous work on using RNNs show an accuracy improvement of 36% when compared to multi-layer perceptrons [20]. Yet, the aforementioned approaches only consider aggregate accuracy and do not consider the accuracy of individual predictions for proactive adaptation decisions.

In the literature, some authors considered the probability that an individual prediction is correct. Maggi et al. [15] use decision tree learning for predictive process monitoring. As a follow up, Francescomarino et al. [7] employ random forests (an ensembles of decision trees) for prediction. Both use class probabilities of decision trees. They analyze how selecting predictions using class probabilities impacts on aggregate prediction accuracy. They observe that using class probabilities may improve aggregate accuracy, but at the expedient of loosing predictions that are below a given probability threshold. Yet, they do not analyze in how far using these class probabilities may improve proactive process adaptation and whether it may offer cost savings.

In our earlier work, we used reliability estimates computed from ensembles of multi-layer perceptrons to decide on proactive adaptation [18, 19]. If the reliability for a given prediction is equal to or greater than a predefined threshold, the prediction is used to trigger a proactive adaptation. In [19] we considered reliabilities computed from ensembles of classification models, which led to cost savings of up to 54% (14% on average). In [18] we also included the magnitude of a predicted violation (computed from ensembles of regression models) into the adaptation decision, which led to additional cost savings of up to 31% (14.8% on average). Yet, we used a fixed point for our predictions (the 50% mark of process execution), and thus did not consider the aspect of prediction earliness.

Problem. Predictions can be made at different points during the execution of a process instance. The point during process execution for which a prediction is made is called checkpoint [13, 22]. When determining checkpoints, there is an important tradeoff to be taken into account between prediction accuracy and the earliness of the prediction [13]. This is particularly important when predictions at a given checkpoint are used as basis for proactive process adaptation.

Typically, prediction accuracy increases as the process unfolds, as more information about the process instance becomes available. As an example, between the 25% mark and the 75% mark in process execution, accuracy may increase by 44% (as reported in [36]) and even by 97% (as reported in [22]). This means later predictions have a higher chance to be correct predictions, and thus one should favor later checkpoints as basis for proactive process adaptation.

However, waiting for the predictions of later checkpoints also means that the remaining time for proactively addressing problems becomes shorter [13]. This can be important as adaptations typically have non-negligible latencies, i.e., it may take some time until they become effective [23]. As an example, dispatching additional personnel to mitigate delays in container transports may take several hours. Also, the later a process is adapted, the fewer options may be available for adaptation. As an example, while at the beginning of a transport process one may be able to transport a container by train instead of ship, once the container is on-board the ship, such adaption may no longer be feasible. Finally, if an adaptation is performed late in the process and turns out not to be effective, not much time may remain for any remedial actions or further adaptations. This means one should choose a rather early checkpoint.

Related Work. In the literature, the tradeoff between prediction accuracy and earliness was approached from different angles. Several authors use prediction earliness as a dependent variable in their experiments. This means they evaluate their proposed predictive process monitoring techniques by considering prediction earliness in addition to prediction accuracy. As an example, Kang et al. [12], Teinemaa et al. [36], and we in our earlier work [20, 22] measured the accuracy of different prediction techniques for the different checkpoints along process execution. Results presented in the aforementioned works clearly show the tradeoff between prediction earliness and accuracy. However, how to resolve the tradeoff between accuracy and earliness was not further addressed.

To increase the earliness of accurate predictions, several authors proposed new variants of prediction techniques. As an example, Teinemaa et al. investigate whether unstructured data may increase prediction earliness and accuracy [35]. Similarly, Leontjeva et al. exploit the data payload of process events to increase prediction earliness [14]. Finally, Francescomarino et al. investigate in how far hyper-parameter optimization [7] and clustering [6] can improve earliness. A similar tradeoff between accuracy and earliness was investigated for time series classification, i.e., for predicting the class label of a temporally-indexed set of data points. The aim is to predict the final label of a time series with sufficiently high accuracy by using the lowest number of data points. Being able to accurately classify a time series early on facilitates early situation detection and thus may help to timely respond to risks and failures [24]. An additional motivation is to reduce the computational effort when compared with using the whole time series for prediction, which is of particular concern for resource- or power-constrained devices [25, 29]. As an example, Mori et al. use probabilistic classifiers to produce a class label for a time series as soon as the probability at a checkpoint exceeds a class-dependent threshold [25]. The aforementioned works address different needs of earliness and accuracy by setting the available parameters, such as prediction reliability thresholds. However, they did not examine in how far the techniques have found a good trade-off between earliness and accuracy. Doing so, requires quantifying the utility of the achieved trade-off, as comparing the techniques solely based on earliness and accuracy may not provide a fair comparison. To quantify such utility, we thus measure how choosing the actual checkpoint for adaptation decisions impacts on overall costs of process execution.

We use RNNs as base learners, i.e., as the individual models in the ensemble, as RNNs can handle arbitrary length sequences of input data [10]. Thus, a single RNN can be employed to make predictions for business processes that have an arbitrary length in terms of process activities. In contrast, other prediction techniques (such as random forests or multi-layer perceptrons) either require training a prediction model for each of the checkpoints or they require the special encoding of the input data to train a single model [16, 22, 36]. However, these encodings entail information loss and thus may limit prediction performance.

RNNs also facilitate the scalability of our dynamic approach. Assume we have c checkpoints in the business process. A single RNN model can make predictions at any of these c checkpoints [5, 34]. If we want to avoid information loss, other prediction techniques would require the training of c prediction models, one for each of the c checkpoints. Our exploratory performance measurements indicate a training time of ca. 8 min per checkpoint for multi-layer perceptrons on a standard PC, while the training time for an RNN was 25 min¹. This means that RNNs provide better scalability for our approach if the process has many potential checkpoints (\(c > 3\) in our case).

We use RNNs with Long Short-Term Memory (LSTM) cells as they better capture long-term dependencies in the data [17, 34]. Our implementation of these RNN base learners is available online². It exploits the Keras library³ running on top of TensorFlow⁴.

However, RNNs also face specific challenges when used for predictive process monitoring. Even though the data that is fed into an RNN is sequential, i.e., a sequence of events, these events represent the execution of business processes which may include loops and parallel regions. Such non-sequential control flows can make prediction with RNNs more difficult [5, 9, 34], as RNNs were conceived for natural language processing, which is sequential by nature [10].

To address these difficulties, we employ the following two solutions (presented in earlier work [20]). First, instead of incrementally predicting the next process event until we reach the final event and thus the process outcome (such as proposed in [5, 9, 34]), we directly predict the process outcome. Thereby, we avoid the problem RNNs may have in predicting the next process activity when process execution entails loops with many repeated activities [9, 34]. Second, we encode parallel process activities by embedding the branch information as an additional attribute of the respective process activity. Thereby, we address the problem that parallel process activities can make the prediction task more difficult [5].

We use bagging (bootstrap aggregating [4]) as a concrete ensemble technique to build the base learners of our RNN ensemble. Bagging generates m new training data sets from the whole training set by sampling from the whole training data set uniformly and with replacement. For each of the m new training data sets an individual RNN model is trained. We use bagging with a sample size of 60% to increase the diversity of the RNN ensembles. Generating the ensembles using bagging also contributes to the scalability of our approach, as the training of the base learners can happen in parallel.

For computing the ensemble predictions \(T_j\) and reliability estimates \(\rho _j\) for each checkpoint j, we employ the strategies defined in [18, 19], because these strategies showed reasonably good results for a fixed checkpoint. Let us assume that at each checkpoint j, each of the m base learners of the ensemble delivers a prediction result \(T_{i,j}\), with \(i = 1, \ldots , m\), where \(T_{i,j}\) is either of class “violation” or “non-violation”.

The ensemble prediction for checkpoint j is computed as a majority vote:The reliability estimate \(\rho _j\) for prediction \(T_j\) is computed as the fraction of base learners that predicted the majority class:

We aim to answer the question in how far determining checkpoints based on reliability estimates (our dynamic approach) compares to determining checkpoints based on aggregate accuracy (the static approach). To this end, we quantify and compare the costs of process execution and adaptation of these approaches.

We employ a cost model used in our previous work [19], which incorporates two cost factors of proactive process adaptation as shown in Fig. 2. The first cost factor is adaptation costs, as an adaptation of a running processes typically requires effort and resources, and thus incurs costs. The second cost factor is penalties, which may be faced in two situations. First, a proactive adaptation may be missed. This can be due to a false negative prediction (i.e., a non-violation is predicted despite an actual violation), or because the reliability threshold was not reached, even though it was an actual violation. Second, a proactive adaptation may not be effective, i.e., the violation may persist after the adaptation.

We consider cost as the dependent variable in our experiments. For each process instance, we compute its individual costs according to the cost model defined in Sect. 4.1. The total costs are the sum of the individual costs of all process instances in our test data set. The test data set comprises 1/3 of the process instances of the overall data set.

We consider the following independent variables (also shown in Table 1):

Reliability threshold \(\theta \in [.5,1]\). As introduced in Sect. 3, a proactive adaptation is triggered only if the reliability of a predicted violation is equal to or greater than a pre-defined threshold, we name \(\theta \).

Relative adaptation costs \(\lambda \in [0,1]\). To be able to concisely analyze and present our experimental results, we assume constant costs and penalties (like we did in [19]). Thus, the costs of a process adaptation, \(c_a\), are expressed as a fraction of the penalty for process violation, \(c_p\), i.e., \(c_a = \lambda \cdot c_p\). We thereby can reflect different situations that may be faced in practice concerning how costly a process adaptation in relation to a penalty may be. Choosing \(\lambda > 1\) would not make sense, as this leads to higher costs than if no adaptation is performed.

Adaptation effectiveness \(\alpha \in (0,1]\). If an adaptation results in a non-violation, we consider such an adaptation effective (cf. Fig. 2). We use \(\alpha \) to represent the fact that not all adaptations might be effective. More concretely, \(\alpha \) represents the probability that an adaptation is effective. We do not consider \(\alpha = 0\) as this means that no adaptation is effective. To reflect the fact that earlier checkpoints may be favored as they provide more options and time for proactive adaptations (see Sect. 2.2), we vary \(\alpha \) in our experiments in such a way that \(\alpha \) linearly decreases over the course of process execution. This means that the probability for effective proactive adaptations diminishes towards the end of the process. To model this, we define \(\alpha _\text {max}\) as the \(\alpha \) for the first checkpoint in the process instance, and \(\alpha _\text {min}\) as the \(\alpha \) for the last checkpoint.

We use four data sets from different sources. The Cargo2000 transport data set⁵ is the one we used in our previous work. The other three data sets are among the ones frequently used to evaluate predictive process monitoring approaches [3, 5, 32, 34, 36]. Table 2 provides key characteristics of these data sets, including the number of checkpoints we used in our experiments.

Using two of the data sets as an example, Fig. 3 gives a first impression of the effect of our dynamic approach. The figure shows the costs of the dynamic approach (bold) and the costs of the static approach for each of the possible checkpoints (dashed). The right hand side of each chart shows the costs without any adaptation (expressed by \(\theta > 1\)). These costs also serves as baseline. We chose \(\alpha _\text {max} = .9\) and \(\alpha _\text {min} = .5\), reflecting the fact that early on in the process there is a high chance that adaptation is effective, whilst at the very end, this chance is only 50%. Also, we show the results for two values of \(\lambda \) (relative adaptation costs). A \(\lambda = .1\) reflects the situation where adaptation is rather cheap, whereas \(\lambda = .4\) a situation where it is more expensive.

The charts in Fig. 3 indicate that the dynamic approach provides cost benefits when compared to the static approach, in particular when adaptations are not too expensive (\(\lambda = .1\)). The charts for more expensive adaptations (\(\lambda = .4\)) show that cost savings may become less, and may even be negative, such as for BPIC2012, where the static approach performs better for three checkpoints.

Also – independent of the static or dynamic approach – it can be observed that if adaptation costs get higher, a higher threshold (and thus more conservative stance in taking adaptation decisions) offers cost savings. While costs for \(\lambda = .1\) are lowest for small thresholds, the situation is exactly opposite for \(\lambda = .4\). The reason is that if adaptation costs are low (smaller \(\lambda \)) carrying out unnecessary adaptations is not so costly and thus it pays off not being too conservative (i.e., setting a lower threshold). However, if adaptation costs are high (greater \(\lambda \)), unnecessary adaptations can quickly become very costly, and thus being more conservative (i.e., setting a higher threshold) pays off.

To further explore the situations in which the dynamic approach offers cost savings, we performed a full-factorial experiment, combining all parameter settings of our independent variables as shown in Table 1. The results for all four data sets are presented in Table 3 for different, selected values of \(\lambda \). For each \(\lambda \), 6666 different situations were explored.

Column A shows the number of situations for which proactive adaptation leads to lower costs than the baseline costs when not performing an adaptation. This is an important metric to contextualize our results, as proactive adaptation may not be beneficial in all situations. In particular, when adaptation costs are high and the chances for a successful adaptation are low, proactive adaptation may not help (e.g., see [19]). As can be seen in column A, the relative number of situations, where proactive adaptation helps saving costs diminishes as \(\lambda \) increases. As an example, while for a \(\lambda = .05\), proactive adaptation is beneficial in 85.4% of situations for Traffic and 75.7% for BPIC2012, this goes down to .8% and 1.4% respectively for \(\lambda = .85\).

Column B shows the number of situations where the dynamic approach has lower costs than the static approach. This indicates that the dynamic approach indeed offers additional cost savings in many situations when compared to the static approach. As can be seen from the last column, the situations in which the static approach has less costs than the dynamic approach, are not very high (at around 3% on average). Again, the dynamic approach offers the highest number of savings for smaller values of \(\lambda \), where the number of situations reach 82.4% for Cargo2000 and even 89.2% for BPIC2017 to give an example.

The actual cost savings of the dynamic approach compared with the static one are shown in Table 4 for different values of \(\lambda \) and \(\theta \). Gray cells highlight where costs of the dynamic approach are less than the costs of the static one (‘0’ indicates that the costs of proactive adaptation are higher than the costs of not performing an adaptation). The table shows the cost savings for selected values of \(\theta \), averaged over all combinations of \(\alpha \).

Higher thresholds imply that cost savings are achieved for higher values of \(\lambda \). As an example, for Traffic a threshold of \(\theta = .6\) allows cost savings up to \(\lambda = .45\), while a \(\theta = .8\) allows cost savings up to \(\lambda = .65.\) The reason is that a higher threshold means that adaptation decisions are take more conservatively. They are taken only if a prediction is highly reliable, which in turn implies that the number of unnecessary (and costly) adaptations are reduced.

However, being conservative comes at a risk. The cost savings for higher thresholds can become smaller than the cost savings for lower thresholds. As an example, while for Cargo2000 a threshold of \(\theta = .5\) leads to cost savings of up to 24%, this goes down to savings of only up to 16% for \(\theta = 1\). And it may even mean that the cost of proactive adaptation is higher than not performing any adaptation, as can be seen for \(\theta = 1\) for BPIC2012.

Overall (i.e, considering all possible situations), the average savings are 9.2% for Cargo2000, 27.2% for Traffic, 15.1% for BPIC2012, and 35.8% for BPIC2017. Across all four data sets, average savings are 27%. We conclude that the dynamic approach can deliver cost savings compared to the static approach, with a high chance that it is better than not performing any proactive adaptation at all.

In addition, the dynamic approach comes with the benefit that there is no need for an up-front decision on which checkpoint to use as basis for proactive adaptation, which is required in the static approach. In particular this means, that there is no need for a testing phase during which aggregate accuracies are computed in order to select a suitable static checkpoint.

Internal Validity. To minimize the risk of bias, we explored different ensembles sizes (ranging from 2 to 100). Literature indicates that smaller ensembles might perform better than larger ensembles (“many could be better than all” [38]). In our experiments, however, the size of the ensemble did not lead to different principal findings. Yet, by using a larger ensemble, we gain more fine-grained reliability estimates than by using a smaller ensemble.

Construct Validity. We took great care to ensure we measure the right things. In particular, we used a cost model that was tested in our previous work. However, we have only used constant cost functions for adaptation costs and penalties. Yet, as we showed in our previous work [18], the shape of the cost functions can have an impact on savings. We aim to investigate the impact of such non-constant cost functions as part of our future work.

Conclusion Validity. As our experiments indicate, the choice of cost model parameters (such as \(\lambda \) and \(\alpha \)) impacts on whether proactive adaptation has a positive impact on cost. To address this threat, we have carefully identified influencing variables and varied them over the whole range of permissible values.