Updating Prediction Models for Predictive Process Monitoring

Updating Prediction Models for Predictive Process Monitoring Alfonso E. M´arquez-Chamorro1,2(B), Isabel A. Nepomuceno-Chamorro1, Manuel Resinas1,2 , and Antonio Ruiz-Cort´es1,2 1I3US Institute, Universidad de Sevilla, Seville, Spain {amarquez6,inepomuceno,resinas,aruiz}@us.es 2SCORE Lab, Universidad de Sevilla, Seville, Spain Abstract. Predictive monitoring is a key activity in some Process- Aware Information Systems (PAIS) such as information systems for operational management support. Unforeseen circumstances like COVID can introduce changes in human behaviour, processes, or computing resources, which lead the owner of the process or information system to consider whether the quality of the predictions made by the system (e.g., mean time to solution) is still good enough, and if not, which amount of data and how often the system should be trained to maintain the quality of the predictions. To answer these questions, we propose, compare, and evaluate different strategies for selecting the amount of information required to update the predictive model in a context of offline learning. We performed an empirical evaluation using three real-world datasets that span between 2 and 13 years to validate the different strategies which show a significant enhancement in the prediction accuracy with respect to a non-update strategy. Keywords: Predictive process monitoring ·Process mining · Process-aware information systems ·Prediction models ·Model updating 1 Introduction Predictive process monitoring (PPM) provides proactive and corrective actions to improve the process performance and mitigate potential risks in real time. PPM retrieves information from Process-Aware Information Systems (PAIS) stored in event logs to make predictions of evaluation metrics, also known as process performance indicators (PPIs) [1]. A path extensively followed in the literature for predictive monitoring is adapting existing machine learning techniques [2] such as decision trees, clustering methods or neural networks to obtain predictive models with higher accuracy. When these approaches are used, the Work funded by grants RTI2018-101204-B-C21 and RTI2018-101204-B-C22 funded by MCIN/ AEI/ 10.13039/501100011033/ and ERDF A way of making Europe; grant P18-FR-2895 and US-1381595 funded by Junta de Andaluc´ıa/ERDF, UE. typical procedure for predictive monitoring comprises two steps. First, a training stage in which the predictive models are trained using data collected in the event logs. Second, once the model is built, it is deployed and it is used to predict PPIs for current and/or future process executions. In the absence of significant changes, ceteris paribus (all else being equal), this approach works fine, but processes are subject to continuous changes. For instance, the response to COVID may introduce new ways of performing activities, users can behave in a different way, or human or computing resources can change over time. These changes may negatively affect the performance of the predictive model since the data used to train them does not reflect reality any more. Therefore, the only way to keep this performance over a desired threshold is by adapting the model to the changes. In the machine learning community, there are two main adaptation approaches for that, namely, online and offline learning. In online learning, the predictive model is being updated continuously from the data it receives. Conversely, in offline learning, the predictive model is rebuilt again from the ground. In this paper, we decide to focus on offline learning mainly for two reasons. Firstly, the pace of change and the pace of new events in the processes we are interested in, gives enough time to completely rebuild new models. Secondly, its use allows one to reuse a huge amount of machine learning techniques that are available for offline learning, which is much more comprehensive than that of online learning. Furthermore, these techniques do not need to make compromises to keep a reasonable learning time. In this context, the goal of this paper is to provide details on how to face two of the questions that arise in the update of predictive models: “Which data should be considered in the new model that is being built?” and “How the selection of data does impact on the performance of the predictive models?”. By answering these questions, we contribute to the state of the art on PPM by proposing six different strategies for updating predictive models (baseline, cumulative, noncumulative, ensemble, sampling, and concept drift) and comparing their performance. Our experimentation was validated using three real-life event logs that span between 2 and 13 years. We have also performed a comparison of different well-known classifiers used in related literature. The reminder of this paper is organized as follows. Section 2summarises basic concepts in predictive monitoring. Section 3presents the strategies for updating predictive models. The experiment and the discussion of the obtained results are presented in Sect. 4. Section 5summarises the related work. Finally, Sect. 6 concludes the work and presents possible future directions. 2 Predictive Process Monitoring In the following, we introduce some basic concepts of predictive process monitoring. As defined in [3], an event log (L) is composed of a set of traces (T). Each trace (Ti) reflects an execution of a process instance. Formally, we can express a trace as an ordered list of events Ti=[Ei1,...,E im] where Ei1represents the first event and Eimthe final event of trace Ti. Similarly, a log can be expressed as the set of traces for the instances that have finished in an interval of time L=[T1,...,T n] where T1is the first and Tnis the last executed trace in the time interval. Finally, an event represents the execution of an activity of the process. Each event contains a set of attributes (a), which represents information related to such event, e.g. timestamp, the resource that executes the activity, or the value of some data used throughout the instance, Ej=[aj1,...,a jo] where o determines the total number of attributes of the event. A process indicator (I) is a quantifiable metric focused on measuring the progress toward a goal or strategic objective. Indicators can be classified into two types: single-instance indicators or aggregated indicators. The former is computed for each trace in the log using the values of the attributes of the events that compose this trace. Therefore, it can be defined as a function of a trace Ti,i.e. I(Ti). This function can return a binary value, e.g a determined condition fulfilled by the trace, or a real value, e.g the duration of an activity. Instead, an aggregated indicator is computed for a set traces by aggregating a single-instance indicator using some aggregation function, e.g. sum or average. An example of this type of indicator could be the percentage of incidents solved in a certain period of time. A predictive model for an indicator Iis a function PI([Eik,...,E il]), with k≤l, that computes a prediction for Ifrom the partial trace [Eik,...,E il], where Eilis the last event that have occurred in trace Tiat a given moment. If k= 1, then all events that have occurred in the process instance at hand are considered. Instead, if k=l, then only the last event of the process instance is considered. In order to train a predictive model ˆ Ifor a key performance indicator (KPI) I, an encoded fixed-size representation Cof all the cases C, where C⊆C, included in the training set is required. This encoding, generally represented as a feature matrix (X), should store enough information of the process, and will be used as input for the machine learning technique employed to build the model together with the value of the KPI Ifor each case in C, which represents the target variable (y). The feature matrix Xis obtained after applying a sequence encoding function F, which receives a set of cases Cand returns a matrix X. Each row of the matrix represents an event E, i.e. the execution of an activity of the process, of a case c∈Cand each column represents the different (encoded) attributes aof the event. Various sequence encoding techniques have been proposed in the literature for this task such as last state encoding [4], aggregation encoding [5], or index-based encoding [6]. The other decision is if only one classifier is trained for the whole dataset or, on the contrary, if cases are grouped into several buckets and a different classifier is trained for each one. Several case bucketing techniques have been proposed in the literature [7]: Zero bucketing [5], prefix length bucketing [6], or cluster bucketing [8]. After these two decisions are made, a predictive model is built using some machine learning algorithm using the pair (X, y) as the input. Fig. 1. Updating models system in a predictive monitoring process. Fig. 2. Training stage. Fig. 3. Run-time monitoring stage. An indicator Ican represent different issues, such as a certain outcome, the next activity of the process or remaining cycle time of a given process case. In this work we have focused on the outcome-based prediction. Therefore, we are predicting an outcome value per case instead of a value per each event. 3 Updating Predictive Models Once the predictive models are generated following the mechanisms described in the previous section are deployed into production, they start making predictions that can be used to timely react to operational issues. However, after a while, the way the process was performed might have changes; resources participating in the process may come and go; even the structure of the process may suffer changes. All these changes are ignored by the predictive model that was deployed some time ago, so these changes may negatively affect the performance of the predictive model. Therefore, it is necessary to provide mechanisms to update the predictive model. Figure 1shows a system for the updating of predictive models described below. It consists of a training stage depicted in Fig. 2(which involves the filtering of the event log, the generation of the predictive model and the evaluation of this model), the deployment of this model, the prediction using this model, and finally, a mechanism for the update of the deprecated models, named Run-time monitoring process as shown in Fig. 3. This mechanism can evaluate the model in terms of the performance of the predictions and decide when the predictive model should be updated according to three possible parameters: the time elapsed from the last deployed model, the accuracy of predictions and the possible occurrence of a concept drift [9]. As mentioned in the introduction, there are two approaches for updating predictive models, namely online and offline learning. In this paper, we focus on offline learning because it allows one to use the huge amount of machine learning techniques for offline learning, which is much more comprehensive than that of online learning and, furthermore, these techniques do not need to make compromises in order to keep a reasonable learning time. To the best of our knowledge, any other work related to offline strategies for updating predictive models appears in the literature, so that comparison with other papers is not possible. In the context of offline learning, two basic questions need to be answered to update the predictive model: 1. When should the predictive model be updated? 2. Which data should be considered in the new model that is being built? For the first question, several strategies can be considered (Run-time monitoring stage in Fig. 3). The most straightforward is a periodical update of the model [10]. A reasonable deadline for the change of the model can be fixed, e.g. six-monthly periodicity, and then, a new generation of the model will be carried out. A different strategy might involve monitoring the accuracy of our predictions. When it begins to decrease over an uninterrupted period of time, it may be recommended to change the predictive model. A threshold of error can be set, and if the prediction exceeds this threshold, the prediction model will be updated. Finally, a third strategy could involve using the detection of drifts in processes [11] to trigger updates in the predictive model [10]. Several strategies could be also combined to design a more robust system. Our focus in this paper is, however, on the second question. This question is relevant because of two reasons that involve the quality and cost of predictive models. Concerning the former, if the reason for updating the predictive model is because the process has changed, it is reasonable to think that learning past behaviours of the process may not be beneficial for the performance of the predictive model, so it might make sense not to include the whole data set, but only the most recent behaviour. As for the latter, the computational cost of building a predictive model increases with the size of the input data set. Therefore, a goal should be to achieve the best predictive performance by using the smallest possible input data set. In [10], authors propose two possible solutions to the second question: retraining and incremental update of a predictive model, however, all predictive algorithms cannot learn incrementally (e.g. random forests). Therefore, we have collected a set of strategies for choosing the data set used for building a new predictive model regardless of the predictive algorithm used. A strategy for choosing the data set used for building a new predictive model can be seen as a function Sthat receives a training and test set pair (X, y)and returns another training and test set pair (X,y), such that X⊆Xand y⊆y. Next we detail several possible data selection strategies. We use the notation X[i,j]to select the subset of Xthat is between iand j, where iand jcould be either an instant in time such as the 7th of March of 2019, or an instance number since the first one received. Furthermore, if they take the value 0, it refers to the first event in the data set and if they take the value c, it refers to the last event received in the data set. Therefore, X[0,c]=X. In the following, we present the different strategies for the selection of data. Figure 5shows a graphical representation of the different strategies described in this section. Figure 4depicts an event log that will be used to explain the different strategies in Fig. 5. This event log is split into several intervals from t1 to tn. Each interval represents all the process instances executed during a certain period of time, e.g. six months. 1. Baseline strategy (SB): In this strategy the model is not updated throughout the life of process: SB(X, y)=(X[0,c],y [0,c]) Figure 5a shows a graphical representation of the baseline strategy. With this strategy, a first interval is selected as the training set, and it is not updated throughout the life of the process. We use the rest of the intervals as test sets. 2. Cumulative strategy (SC): This strategy involves including all the cases that are available for training since the beginning: SC(X, y)=(X[0,c],y [0,c]) Cumulative strategy is represented in Fig. 5b. This strategy involves adding all instances of a process as training set. We split the event log into training and test sets, and we incrementally add each interval from t1to tnin the training set and use the rest for the test set. 3. Non-cumulative strategy (SN): This strategy involves choosing only the most recent cases for training. It includes a parameter tn that determines how many recent cases should be included in the training: SN(X, y)=(X[c−tn,c],y [c−tn,c]) The advantage of this strategy in comparison to the cumulative strategy is that it is more efficient computationally and it might solve problems derived from using cases that do not follow the current behaviour of the process. The drawback is that having less training instances might hurt the performance of the predictive model. For the non-cumulative strategy (Fig. 5c), we select an unique interval in the training phase. In this manner, we only include the most recent cases for training. 4. Ensemble strategy (SE): This strategy is similar to the non-cumulative strategy because it only includes the most recent ts cases in training a new model. The difference is that, unlike the non-cumulative strategy, this strategy do not throw away older models, but keep them and combine them using some ensemble technique [12]. For instance, one can use a weighted voting technique in which the prediction of each model is considered a vote and combined using different weights for each model to make the final prediction. These weights can be updated each time a new model is added to the ensemble so that older models have a lower weight. To this end, weights can be modeled using an exponential decay function like e−λt. Furthermore, besides these weights, if the last model had very bad performance, we might be interested in removing it from the ensemble so that it does not hurt the overall performance. To this end, we set a threshold parameter so that if the quality metric of choice, e.g. f-score, of the previous model did not meet the threshold in the last interval, it is removed from the ensemble. The advantage of this strategy is that it has almost the same computational cost as the non-cumulative strategy, but it helps to avoid discarding all of the old cases. However, the combination of the different models might not be as powerful as a model built using the cumulative strategy that includes all previous cases. In this strategy, depicted in Fig. 5d, we choose the same training and test sets and keep older models to combine them using some ensemble technique to achieve better predictions. 5. Sampling strategy (SS): This strategy involves a weighted sampling of all the cases that are available for training since the beginning. It includes a parameter ts that determines the number of samples that must be obtained from the data: SS(X, y)=(sampling(X[0,c],ts), sampling(y[0,c],ts)) Where sampling is a function that takes ts samples from Xor y, respectively. Sampling can also be weighted so that it is more likely to obtain more recent samples than older samples. A similar approach as the one used in the ensemble strategy can be used here to define these weights. The advantage of this approach in comparison to the cumulative strategy is that it limits the computational cost of the new model. Furthermore, unlike the ensemble strategy it relies on the machine learning algorithm instead of in the voting mechanism to combine both information from old and recent cases. Fig. 4. Representation of a split event log. Figure 5e shows the Sampling strategy. We build the training set in a incremental way using a weighted strategy where recent samples are more likely to be selected than older samples. 6. Drift strategy (SD): This strategy is similar to the non-cumulative one. It includes the most recent cases for training and, when a concept drift is detected, we include as training set, all the cases after a certain time has passed since the drift has occurred. Figure 5f shows the drift strategy. When the concept drift is detected, training set is built only with those cases executed after the drift detection. 4 Experimental Evaluation As we stated in Sect. 1, the goal of this paper is to define the different strategies for the selection of data (described in Sect. 3) and compare the predictive performance of the different strategies proposed. Based on this goal, we define a research question for our experimentation: What is the impact of the different updating strategies on the accuracy of predictions? The rest of the section is organized as follows: the experiment setup is detailed in Sect. 4.1. The different datasets used in the experimentation are described in Sect. 4.2. Finally, a discussion of the obtained results is provided in Sect. 4.3. 4.1 Experiment Setup As predictive algorithm we have used random forest [13] as seen in previous works in the literature [14]. This technique combines predictor trees such that each tree depends on the values of a random vector tested independently and with the same distribution for each of them. In [14], authors highlight extreme gradient boosting (XGBoost) and random forest as two of the best techniques in predictive monitoring. Thus, we have selected random forest because the quality of results with respect to XGBoost is similar and it consumes less computational time. We have selected a typical aggregation encoding described in [14] as one of the most used in the literature to encode the process cases and also one of the best performers [14]. Thus, all events since the beginning of the case are considered. An aggregation function is applied to the values taken by a specific attribute throughout the case lifetime. In our case, this function is the number of times that each specific attribute appears in the case (frequency encoding). We have not divided the cases in the event log into different buckets. This technique is named Zero bucketing as defined in [14]. We have also incorporated the order of the events as a new attribute in all the logs, as well as the elapsed time between Fig. 5. Graphical representation of different proposed strategies for choosing the data set used for building a new predictive model. the event and the beginning of the case and the time between the previous event and the current one. The details and the code of the experimentation are available online1. 4.2 Event Logs Three different real-life event logs were considered in our experiments: IT Department of an Andalusian organisation (ITA), BPI 2015 (BPI15) [15] and Traffic fines (TRAFFIC) [16]. These logs were chosen because they span several years: 2, 5 and 12, respectively, so they are useful to evaluate the effect of possible changes on the process over time. 1https://github.com/isa-group/predictive-monitoring-evolution.