One of probabilistic methods available for such analysis is Bayesian belief network (Darwiche, 2008). It allows to represent a set of variables and their conditional dependencies via a directed acyclic graph. For example, given some known information about client, whether the process will execute successfully.

The Bayesian belief network could be used to answer questions important to business process owners by exploiting general probability calculations:

The belief network contains two components – a DAG that represents variable dependency and CPTs that represent probabilities. Based on previous section, this is very suitable for event log transformation. In the event log, event sequences are stored and each unique event could be represented as a node in a DAG and data dependency of events could be represented by the CPTs. While nodes transformation is not a hard task, arc between nodes creation is not so easy, because they reflect conditional dependency in the Bayesian belief network and transitions between events in the business process, therefore the task of DAG creation becomes complex.

Process Mining methods focus on applying data-mining methods on data existing in information systems that represent historical execution of business processes (Verbeek et al., 2010). This data comes in a form of an event log which consists of data collected from various sources. There are a few ways to represent event logs, but the most common one is the XES file format (Günther and Verbeek, 2014) – a standardized and extensible file format. It is extensible and allows addition of domain specific data about business process execution. The event log contains general information on execution of the business process, such as trace identifier to identify process instance and a list of events with occurrence timestamp and identifier (Table 1). Each trace and event might also contain any other additional data related to the behaviour, e.g. client names, ages, locations, system specific information such as subsystem, server, etc.

In the scope of this paper, Event Log definition used for transformation, is based on van Dongen et al. (2008) and adapted from previous work (Savickas and Vasilecas, 2014) and is defined as follows:

One of the components of the Bayesian belief network is a directed acyclic graph. Business processes expose complex behaviour, such as parallelism, repeated execution of activities, loops and others. This causes standard process models that are based on graph theory to be unusable for Bayesian belief networks since they can expose the same cyclic behaviour and are not acyclic.

Event logs contain data on events that have occurred in the process. The information on the sequencing of specific events is hidden in the log and needs interpretation to understand what events can and what events cannot follow each other. In order for those event sequences to be transformed into a directed acyclic graph, a labelled state transition system can be used. In this transition system, each event has a unique label and no cycles are formed, because repeated events have unique labels. This way, event sequences are represented as a unique path between states, where a state is never accessed twice. For example, sequences { a , b , c , b , d , e } and { a , b , c , d , e } in an event log would be represented as state transition sequences { { a , b } , { b , c } , { c , b 1 } , { b 1 , d } , { d , e } } and { { a , b } , { b , c } , { c , d } , { d , e } }.

Van der Aalst et al. (2011) used state transition system to predict process instance duration and each state was for either a set of events that occurred, or event sequences that have occurred. We believe that process work-flow analysis is best represented by event sequences, therefore we choose to represent each state as a sequence of events and their data.

The definitions of trace state and event state are not clearly defined in van der Aalst et al. (2011), therefore we introduce the definitions for use in the CPT construction.

Event state describes attributes and their values that belong to the specific occurrence of an event in a trace, therefore we can reuse the definition of μ in the event log definition:

A state of a trace is a collection of event states, therefore it can be defined as:

While the labelled state transition system in the referenced paper is used for some general attribute prediction, it does not provide any prediction functions for attribute or sequence predictions, therefore it is used only as directed acyclic graph representation in Bayesian belief network. The state representations are used for observations used in conditional probability calculations.

For a Bayesian belief network to be constructed, we start with an event log. Usually, process execution data is stored in information systems in many different places and forms. Data collection regarding business processes is always a context-dependent task. That is because each organization has unique information system implementations and their business process differ from one organization to another. Due to this reason, our approach ignores the data collection task and assumes that an event log is present as defined in Section 3.2.

After collecting data and creating an event log, the construction of belief network can be started. The overall approach is depicted in Fig. 1 and is done in a sequence of steps as follows:

CPT aggregates data in the event log for each event and its’ parents into a single table where each attribute combination is assigned a probability. Therefore, is is defined as:

The CPTs for the DAG are constructed as follows:

Business processes, once automated in an information system, have a controlled work-flow. During this work-flow, performers of the process generate data with regard to the process execution, such as location, organizational resource or other domain specific data, e.g. student group, faculty, etc. This data, once taken as a whole, allows to detect causality between events or between data parameters.

Usual approaches for analysing business process execution is to use statistical data, such as averages, maximums, minimums, sums, frequencies and others. While this does provide a means to infer how the process behaves, it could be superficial, because it might not take conditional dependencies between data. For this, we believe that Bayesian inference could be used for decision support, because it provides reasonable expectations.

Bayesian inference derives the posterior probability using well known Bayesian inference formula (Darwiche, 2008): P ( H | D ) = P ( D | H ) × P ( H ) P ( D ) .

In here, P ( E | H ) is the posterior probability of a hypothesis H based on evidence D, which is a consequence of two antecedents – the prior probability P ( H ) and a likelihood P ( D | H ) with a marginal likelihood P ( D ).

For business processes, the hypothesis is any set of event attributes and values whose probability we would like to infer, for example, “what is the probability of the claim status to be declined?”, where claim is the event, status is the attribute and declined is the value.

The hypothesis is not limited to a single { e , m } tuple. Since business processes can drift and mutate in time, we limit the possible choices for hypothesis only to those attribute and value pairs which have been seen before in the trace.

Since hypothesis contains multiple possible elements, the prior probability is calculated as a product for each of the attribute values to occur with no conditions, i.e. P ( H ) = ∏ i P ( h i ) = ∏ i ω ( h i ) .

In standard statistical methods, only the number of times when H | E occurred would be used for inference, but this is not really useful for decision support, because it does not take into account the marginal likelihood and only shows a number of times it has been seen regardless of the likelihood of each of the parameters, i.e. not only how often this hypothesis has been seen before, but also how likely is it to be seen given current evidence. Therefore, for inference, we need to use the evidence likelihood. We assume that the inference is done in the context of a single process instance, therefore the evidence is the current state of the trace of the process.

Given the definition of the evidence, marginal likelihood can be calculated as a sum of all probabilities for the evidence to occur with the subsets of hypothesis, i.e. P ( D ) = ∑ i P ( D | h i ) × P ( h i ) = ∑ i ( f ∏ j P ( d i | h i ) ) × P ( h i ) = ∑ i ( ( ∏ j ω ( d j ) / ω ( h i ) ) × ω ( h i ) ) .

Finally, the prior likelihood is the probability to see the evidence given the hypothesis and it can be calculated as P ( D | H ) = | D × H ∈ M | | D | , i.e. the number of times the evidence has been seen together with the hypothesis divided by the number that the evidence has been seen in general.

Having all of the components, we get the final inference formula: P ( H | D ) = | ω ( D ∩ H ) | | ω ( D ) | × ∏ i ω ( h i ) ∑ i ( ( ∏ j ω ( d j ) / ω ( h i ) ) × ω ( h i ) ) .

For formal verification of the approach, domain specific questions should be ignored and there needs to be an objective testing. Therefore it was decided to test the approach with event logs and calculate probabilities of already known values and see whether it is capable of achieving high probability rates.

The event logs used in experiments should be with multiple complexity levels. For this, a synthetic log (SL) and two publicly available logs were chosen (Table 2). The publicly available logs were of a Dutch Financial Institution event log (DL) taken from Business Process Intelligence Challenge 2012 (van Dongen, 2015a) and Municipality event log (ML) from Business Process Intelligence Challenge 2015 (van Dongen, 2015b). The ML log contains time stamp or unrelated attributes activityNameNL, dateFinished, dueDate, planned, datestop and during experiments they are ignored.

The experiments were done independently for each event log as follows:

The experiment itself is performed by imitating the execution of a business process. The system iterates through each event creating a partial trace with a state l state ( σ ), where σ is currently iterated part of the trace in the event log. Knowing what the last event with a state l event ( σ ( k ) ) is, we calculate P ( l event ( σ ( k ) ) | l state ( h d k − 1 ( σ ) ) ) – the probability for the event’s state, given the already occurred events in the partial trace. Probability calculations are done only when | σ | > 00$]]>, i.e. at least one event is in the partial trace. This is done, because we are not interested in the first event in the trace – its’ probability does not have any conditional dependencies, therefore it does not test the approach.

After completing the experiment for each of the event log for the 5 times, the average probability is calculated for each event. This allows to see what is the general capability of the approach. Results, where probability is equal to 0 or events that have occurred less than 5 times are rejected as noise. The probability equal to 0 is rejected because it has some data that has never occurred in the event log, therefore decision support for such cases is impossible and it does not answer whether the approach is any good. The rarely occurring events are also rejected, because they do not appear frequently enough for reliable results.

The selected experiment process allows to see how the proposed approach behaves with different attribute counts and differing complexity of the event logs. The approach was implemented in a prototype tool. The prototype tool is called BBNGs (Business process Belief Network enGine) and implemented using. NET framework. The BBNGs is a tool designed to receive an input event log of a business process, transform it into belief network and allow inferences on the belief network. The overall architecture is shown in Fig. 2.

The main component responsible for the behaviour of the tool is controller and it exposes the behaviour to the GUI. Graphical user interface is used by users to perform actions like setting source files, performing observations, or previewing extracted graphs and inference results to the user.

The initial task is to receive input in the XES format from an external system. The specific input format was chosen, because, as described previously, most of the time information systems have no clear event logs of business processes and the data might be heterogeneous. The XES parser component loads the data into the BBNGs and makes the event log accessible in memory.

Afterwards, a component for each of the steps described in previous section is present – DAG Extractor for extracting labelled transition system and the directed acyclic graphs from an event log, CPT Builder for creating conditional tables and inference engine which is responsible for observing variables and performing inferences. Inference Engine component is responsible for making inferences on the generated belief network. It is used by UI component to make required inferences and allow extraction of knowledge about business processes.

The experiments resulted in a total of 17750 trace runs with a total of 207316 events (Table 3). From all of the probability inferences, 87170 of them were rejected as unsuitable, because they had data not available in the training set, were anomalous with P ( D | H ) = 0 or because they were the first event in the trace. The inference results are visualized in Fig. 3.

From all of the inferences taken into account, the highest average probability was for synthetic log, as expected. This was due to the underlying process being rather simple. The inferences were successful on average 77% of time with 4 of the events having inferred probability on average higher than 99% with deviation <1%. Other events had the average probabilities spanning from 31% to 82% with deviation ranging from ±38% to ±49%.

Other processes were much more complex, having many more possible data variations. This resulted in a lower average probability. In the case of DL log, the events contained barely 3–4 data attributes, therefore their causal dependency is arguable. This resulted in average probability of 52%, but 10 out of 36 events had average inference probability higher than 80%. 3 events in the DL log were ignored in inferences, because either they were always the first event or have occurred less than 5 times in each of the test sets.

The ML log has the lowest results regarding calculations taken into account (11787 out of 43435), but the process itself is the most complex, because the log has 289 unique possible events and only 1156 traces in total. This causes the belief network to be under-trained due to such complex structure and low amount of data. Also, it had usable inferences only on 42 out of possible 289 events. Ignoring that, it had average probability of 95%. Even more so, in total 39 events out of 42 taken into account had the average probability higher than 80%.

To sum up, the experiments show that the approach is usable, but it relies heavily on data – in case attribute values are observed that have never been observed, or if there is limited amount of historical observations which do not fully cover the process behaviour, the approach has limited use. But for events whose behaviour is expressed in the event log, the proposed approach shows great results and allows to answer questions important to the execution of processes – whether events are expected in the process instance, what data might occur there and others.