On the use of domain knowledge for process model repair

A process model (M) is a description of the business process. It represents the sequence of process events (i.e., the activities and control-flow of the process). Usually, this is represented as a directed graph where the nodes represent the events and the edges represent the potential flow of control among the events. An event log (L) is a multi-set of traces and each trace (T) represents the execution of a process instance, (i.e., the sequence of process activities). Techniques for automatically discovering a process model from an event log were proposed in the literature [3]. The final process model is expected to conform to the event log (i.e., the model M is expected to replay all the traces T in L).

The event log represents the observed behavior while the model represents the expected behavior. Over time, the expected and the observed behavior may not align anymore, for instance because of concept drift [10]. In this case, process model repair [15] may be applied. Process model repair aims to improve the quality of a model through process data by applying minimal changes to the initial model. Existing methods take as input a model and an event log, and produce a new model that resembles the original one as much as possible while still guaranteeing that the new model is able to replay the traces in the log.

Figure 1 illustrates the process model repair schema.

In more detail, process model repair techniques need two inputs: a process model and an event log. A process model typically uses a graph-based notation to express the partial order relation of the activities within the different traces constituting the event log. Such model may have been designed manually by a person using a modeling tool or may have been generated by a process discovery tool. An event log typically comes from an information system (e.g., a BPMS, a database, etc). The data present in the event log may record events about a large amount of time, including time periods in which the process is enacted differently (i.e., the actual process changed with respect to its model). This means that the initial model is no longer able to accurately describe the behavior recorded in the event log, especially when it comes to newer traces. Thus, the task of model repair is that to produce a new process model that is able to best describe all the facts and relations observed in the event log.

Let us consider the example illustrated in Fig. 2. In the upper part, the input of the model repair technique is depicted, that is, a process model (left) and an event log (right). The process model can be expressed in any modeling language. In this example, circles represent events, labeled rectangles represent activities, diamonds represent choices and arrows represent ordering relations. The activities in the process model are labeled with capital letters denoting the type of activity. In the event log, traces contain sequences of instances of the activities denoted with small letters. The lower part depicts the result of the model repair technique. The green components represent newly introduced parts. The repair technique starts by replaying the event log in the initial model and checking conformance of the traces. The input event log has four traces. Traces 1 and 2 are conformant (i.e., they can be replayed by the initial process model) while traces 3 and 4 are non conformant (i.e., they cannot be replayed by the initial process model). Trace 3 has a final event f that is not expected according to the model. As a possible repair, activity F is included in the model as an alternative flow after activity E. For trace 4, events j and k are not instances of any activities of the model. As a repair, the sequence J followed by K is included in the model as an alternative flow after activity A. With these repairs both not previously replayed traces are then replayed by the final process model, improving the fitness [16] of the model.

Process model repair can be positioned in between process discovery [3] and conformance checking [5] (i.e., taking a predefined model as the norm and checking whether the event log complies with it). The final model may reflect reality (i.e., observed behavior recorded in the event log) better than the initial model, but may also be very different from it, which can make the final model useless in practice. For instance, practitioners may heavily rely on the initial model to understand how a particular process functions. Presenting to them a model very different from the one they are accustomed to may result in the final model being ignored by them. To address this issue, a minimality criterion is considered when repairing the initial model guaranteeing that the final model is as similar as possible to the initial one. However, the minimality criterion does not guarantee that still important parts (e.g., commonly agreed pieces of the process that represent a shared understanding of the work) are not changed by the technique. In this paper, I argue that the repair would be more useful to the practitioners if it takes into account predefined fragments of the model that they do not want to modify.

Furthermore, as stated in [17, 18], existing approaches for process model repair are applied to the whole event log. They apply the changes based on all the traces that did not comply with the model, thus including traces that the practitioners do not want to take into account for the repair. As a consequence, the final models is unnecessarily complex and harder to understand by the practitioners. In this paper, I also argue that the repair technique can benefit from a pre-processing step, in which the relevant traces for the repair are identified.

A theory revision technique receives as input an initial logical theory (\(T_i\)) and a set of factual data (C). The theory is composed by a set of logic rules and can be either specified manually by domain analysts or automatically learned using an Inductive Logic Programming (ILP) system [9]. Furthermore, the initial theory is divided into two parts: an unchangeable part, which is assumed to be correct, and a changeable part that can be modified by the revision. The data are split into positive (\(C_p\)) and negative (\(C_n\)) observations. The final theory (\(T_f\)) should logically imply all the positive observations (completeness) (\(\forall c_p \in C_p, T_f \vDash c_p\)), none of the negative observations (consistency)(\(\forall c_n \in C_n, T_f \nvDash c_n\)) and satisfy a criterion of minimality [7]. Figure 3 illustrates the theory revision schema.

In more detail, theory revision needs two inputs: an initial theory and a dataset. The initial theory is an approximately correct (i.e., only a few parts of the theory is preventing it from correctly explaining the dataset) set of logical rules, and it is divided into two parts: a changeable set of rules and an unchangeable one. The approximately correct requirement guarantees that revising the theory is more beneficial than relearning the theory from scratch, given that only a few parts of the theory are preventing it from correctly reflecting the dataset. Rules may be expressed in first-order logic notation (e.g., Horn clauses). These rule sets may have been specified manually by a practitioner or may have been learned via a machine learning technique. A dataset is a collection of facts that may come from an information system (e.g., a database). The data present in the dataset is divided into two sets: the positive and the negative sets. The positive set represents facts that must be explained by the theory whereas the negative set represent facts that must not be explained. The task of theory revision is to generate a final theory in which all the unchangeable rules of the initial theory are still present and some changeable rules have been replaced by new ones.

When applying theory revision, three considerations must be made. First, it must be clear where the theory should be modified (revision points). Second, it must be clear how the theory should be revised (revision operators). Third, it must be clear what evaluation function is going to be considered in order to choose the best revision.

Revision points are defined through the data. Positive observations define generalization revision points while negative observations define specialization revision points. The first are the literals in a rule responsible for the failure of proving a positive example (failure point) and other antecedents (contributing points) that may have contributed to this failure. The second are defined by clauses used in successful proofs of negative examples. The specification of a revision point determines the type of revision operator that will be applied to make the theory consistent with the data. Generalization operators are used when a positive observation is not proved by the theory, i.e., the theory must be more generic in order to explain a positive observation. The second group is applied when a negative observation is proved by the theory, i.e., the theory should be more specific in order to not explain a negative observation.

Theory revision relies on operators that propose modifications at each revision point. Any operator used in machine learning of first-order logic can be used in a theory revision system. For instance, the specialization operator delete-rule, that deletes the rule that is causing the proof of a negative observation and the operator add-antecedent, that adds antecedents to a rule in an attempt to make negative observations unprovable. As examples of generalization operators, we can consider the delete-antecedent operator that deletes antecedents from a rule making this rule more generic and therefore allowing the proof of positive observations previously not proved by the theory. Another operator is the add-rule operator. This operator leaves the original rule in the theory and generates new ones based on the original rule in two steps. First it copies the original rule and, using hill-climbing antecedent deletion, deletes antecedents without allowing any negative observation to be proven, and also those that allow one or more previously unprovable positive observations to be proven (even if doing so allows proofs of negatives). Then it creates one or more specializations of this core rule using the add-antecedents operator, to allow proofs of the desired positives while eliminating the negatives. An evaluation function such as accuracy is used to select the best proposed revision to be implemented.

The main motivation for repairing an existing model instead of re-learning it from scratch is to try to keep the repaired model as similar as possible to the original one. The reason for that is that learning a model is not a trivial task. Very often automatic discovery techniques learn complex models and do post-processing with the goal of simplifying them [20]. The final model must be useful to the practitioners. The manual specification of the model is also not an easy task, being very time demanding and complex, sometimes requiring many interactions between the process stakeholders until convergence to a final model. The point is that the current model, although not up-to-date can have many fragments that still cope with the business and/or reflect an understanding that the process stakeholders want to keep.

This paper argues that a model repair procedure should be flexible to allow the specification of fragments of the model as unchangeable, while the rest are tagged as changeable. Repair proposals will only be applied to the changeable fragments of the model. The idea of fragmenting a process model has been investigated when learning a process model from scratch [21]. Techniques for decomposing a process model (e.g., [22]) can be used for defining fragments of the model that can be changed and the fragments that should remain unchanged. The distinction between the fragments that can be changed from the ones that cannot is a manual task performed by the practitioners.

Information Systems such as enterprise resource planning (ERP) store their execution information into event logs, which are a powerful source of observed behavior. Event logs are stored using the IEEE XES (Extensible Event Stream)¹ format. Its quality should be checked before running any process mining technique (or process model repair technique), given that the quality of the final model is closely associated to the quality of the event log. Techniques such as the one presented in [23] may be used to assess the quality of the event log. Usually, process model repair approaches consider these observed traces as acceptable behavior of the process and guide the modifications in the model with the aim of complying with these traces. However, some of these trace may represent undesirable behavior, e.g., unsuccessful process execution or violation to an external regulation, and they should be separated from the desirable ones. Furthermore, some behavior that was prevented from happening, e.g., with constraints implemented in the information system, is not stored in these logs, given that they were never observed. Such behavior is still relevant to be known during the repair procedure to guarantee that a repair proposal will avoid it and therefore support practitioners on preventing them from happening in the future. I argue that the model repair task should consider positive and negative observations of the process, i.e., it should rely on a set of desirable and undesirable process instances.

The definition of the set of positive and negative traces can be made manually, semi-automatically or automatically. The starting point in all the cases is an event log. In a manual generation the practitioner goes over the event log and distinguishes desirable and undesirable behavior defining positive and negative event logs, respectively. The inclusion of additional behavior is also possible, specially in the negative event log to represent behaviors that were never observed and one wants to guarantee that the final model will not replay them in the future.

For defining the event log automatically, some strategies can be considered. For instance, one can assume that the whole event log represents desirable behaviors and has high quality, defining the positive event log. For the generation of the negative event log some existing techniques may be applied. In [24, 25], the authors propose a tool to simulate declare rules and generate an event log that satisfies those rules. This technique can be used for generating the negative traces, i.e., defining unacceptable behavior as declare rules and simulating these rules. In [26], the event log was enriched with negative events. A negative event was considered by the authors as an event never observed in the event log, meaning an event prevented from happening. The traces generated with negative events may compose the negative event log.

In most scenarios, a manual definition of the positive and negative event log may be impractical. Conversely, automatic approaches may be able to find positive and negative event log, but they may lack quality which can compromise the quality of the final model. In this direction, semi-automatic approaches are suitable for the task. For instance, in [27], the authors propose a combination of different filters that partition the event log in two sets, the first one is composed by the traces that satisfy the filters and the second is composed by the remaining traces. A process model is learned from each of the sets. This approach could be used for generating the positive and the negative set of traces, i.e., the filtered traces would represent the positive observations while the unfiltered traces would represent the negative observations. The practitioner defines the filters accordingly to her understanding of the domain guiding the split into positive and negative event logs. In [28], Key Performance Indicators (KPIs) are used to filter out traces that follow some KPIs and these traces are used for the repair. This approach can be used to generate the positive and negative event logs, e.g., traces that align with the KPI are included in the positive event log and traces that do not are included in the negative event log.

As in any model learning approach, the quality of the repaired model is directly related to the quality of the input data, i.e., the positive and the negative event logs. Therefore, existing approaches for evaluating the quality of the event log, e.g., checking for missing events (i.e., events that occurred in the IS but were not recorded) or log errors (i.e., events that did not occur, but were stored in the event log) and improving it when necessary can be used as a pre-processing step to guarantee that the provided positive and negative event log have the necessary quality for the repair task.

In this section, I sketch the main steps one should consider when developing a process model repair technique that incorporates practitioner knowledge or when extending an existing technique. Algorithm 1 depicts the top level algorithm for a process model repair framed as theory revision problem. The algorithm receives as input an initial process model (\(M_i\)) with the specification of the fragments that should remain unchanged (\(M_u\)) and the fragments that can be changed (\(M_{c_i}\)) during the repair, an event log (L) partitioned in positive event log (\(L_p\)) and negative event log (\(L_n\)) and an evaluation function (e.g., fitness). It returns as output a final model (\(M_f\)) composed by the unchanged fragments (\(M_u\)) and revised fragments (\(M_{c_f}\)).

The algorithm starts by generating the revision points which are parts in \(M_{c_i}\) where deviations were found. Conformance checking [5] techniques can be used for this task. When incorporating practitioner knowledge, the process model repair technique designers must keep track of the two possible types of revision points, generalization or specialization revision points. The former are sequences of activities that did not replay part of a positive trace and the latter are the sequences of activities that allowed a negative trace to be replayed.

Then, for each revision point, proposals of repair are made. At this point, the designers also must consider two types of revision operators, generalization or specialization revision operators, that would be applied correspondingly to the types of revision points. Different revision operators may be applied, e.g., for including an activity or a sub-process or removing infrequent activities. Each of these proposal repairs are then evaluated considering an evaluation criterion, e.g., fitness [16]. Also, a minimality criterion should be considered and proposed changes that affect the model minimally should have preference over changes that entail a bigger modification, e.g., given that the evaluation function returns the same value, the repair that includes less activities should be preferable. The repair that improved the most the model is the one implemented. The repair finishes when the model cannot be improved anymore, i.e., the value of the evaluation measure can not be improved anymore.

The core of the algorithm is the input in which the practitioners are able to contribute by defining unchangeable fragments (\(M_u\)) and providing acceptable (\(L_p\)) and unacceptable (\(L_n\)) behaviors. The identification of the revision points and the definition of the revision operators are a decision for the process model repair approaches designers. And existing process model repair approaches can potentially be extended by receiving the new inputs and by proposing changes on their repair technique to consider them.

To illustrate how to frame the process model repair problem as a theory revision problem, I chose the process model repair technique proposed in [29], given that it is the available technique more closely related to the concepts proposed in this paper. Section 5 describes in detail the analysis of the available techniques.

For the event log, I used the Process Discovery Contest 2021 data set². The dataset contains 480 training logs, 96 corresponding test logs, 96 corresponding ground truth logs, and 96 process models. The dataset was generated from a base model, which was inspired by a model discovered from a real-life event log. The logs are all stored using the IEEE XES file format, while the models are workflow nets (a subclass of Petri nets) stored in a PNML file. I randomly chose an event log from the set of test logs and its corresponding process model. The event log (L) contains 250 cases with 7097 events. The process model (\(M_i\)) has 50 transitions and 44 places and it is depicted in Fig. 5, where circles represent places, squares transitions and black squares silent transitions (transitions that are not stored in event logs). I use fitness as the evaluation function (ef). The fitness of the event log with respect to the initial process model is 0.76. Considering a threshold of 0.70 for the fitness, it justifies to repair the initial model instead of discovering a new model from scratch.

As regards the inputs of the model repair procedure, I manually chose the fragment of the model that should kept unchanged, and I used filtering based on an activity to automatically split the event log. For that, I used the Filter log by attributes plugin from the UMA package in the Prom toolkit³. For model repair, I used the approach proposed in [29] through its plugin “Repair Model” implemented in the Prom toolkit. The revision points are identified by using conformance checking and the revision operators focus on including sub-processes or loops to the current model. The approach was run with its default parameters, except for the parameter concerning the removal of infrequent nodes which was set to not remove infrequent nodes.

As a benchmark, the repair approach was applied to the initial process model (\(M_i\)) without setting unchangeable fragments, and to the event log (L) without partitioning it. The fitness of the repaired model (\(M_f\)) was 1. \(M_f\) is shown in Fig. 6.

Analyzing the initial fragment of \(M_i\) and its repair \(M_f\) (see Fig. 9 (a) and (b) respectively), it is possible to observe that transition t09 was not always executed. In a first scenario (Scenario 1), a practitioner considers that this optional behavior is an unacceptable behavior (e.g., it represents a regulation), and therefore she wants to indicate that the sequence flow transition t09 followed by transition t10 must always happen. Then, this fragment of \(M_i\) was manually set to unchangeable (\(M_u\)). Given that the approach presented in [29] does not consider the concept of changeable and unchangeable fragments, in order to simulate it, I renamed the transitions to unknown labels. With that, it is expected that the repair approach would not change the behavior described by this fragment, given that it was not observed in the event log, and it would not remove it, given that the input parameter was set to keep all nodes including infrequent ones. All the rest of fragments of \(M_i\) are changeable (\(M_{c_i}\)) for the repair approach. The repair approach runs receiving as input \(M_i = M_u \cup M_{c_i}\) and L. The repaired model (\(M_f = M_u \cup M_{c_f}\)) can be seen in Fig. 7 and its initial fragment in Fig. 9 (c). The fitness of the repaired model (\(M_f\)) was 1. It is possible to see that the initial fragment is kept, but the traces containing the undesired behavior, i.e., execution of transition t10 without the execution of t09 before, were considered by the repair approach and changes in the model were done in order to fit these traces. In Scenario 2, the practitioner wants to enforce that these are undesirable behavior that should not be replayed by the final process model. The event log is partitioned with traces that contain t09 representing desirable behavior (\(L_p\)) and the traces without transition t09 representing undesirable behavior (\(L_n\)). Event log \(L_p\) contains 178 traces while \(L_n\) contains 72. The repair approach runs receiving as input \(M_i = M_u \cup M_{c_i}\) and \(L=L_p \cup L_n\). The repaired model (\(M_f = M_u \cup M_{c_f}\)) is depicted in Fig. 8 and its initial fragment is shown in Fig. 9 (a) having the same initial fragment as the initial model. The fitness of the repaired model (\(M_f\)) was 1.

With this illustrative scenario of use, it was possible to show that the final model depends on the choices made for the inputs and the practitioner plays an important role in setting these inputs appropriately. Being the domain expert, the practitioner is able to identify the parts of the model that should not be changed and also the relevant data that should be considered for the changes. Although the fitness of the repaired models found for the Benchmark, Scenario 1 and Scenario 2 are the same, their structure is different representing different behaviors. The ones in Scenario 1 and Scenario 2 reflect practitioners needs. It is worth mentioning that none of the existing approaches for process model repair provide a tool for directly implementing the ideas discussed in this paper. In the following section, I analyze the existing approaches in more detail.