Motivated by the abundance of uncertain event data from multiple sources including physical devices and sensors, this paper presents the task of relating a stochastic process observation to a process model that can be rendered from a dataset. In contrast to previous research that suggested to transform a stochastically known event log into a less informative uncertain log with upper and lower bounds on activity frequencies, we consider the challenge of accommodating the probabilistic knowledge into conformance checking techniques. Based on a taxonomy that captures the spectrum of conformance checking cases under stochastic process observations, we present three types of challenging cases. The first includes conformance checking of a stochastically known log with respect to a given process model. The second case extends the first to classify a stochastically known log into one of several process models. The third case extends the two previous ones into settings in which process models are only stochastically known. The suggested problem captures the increasingly growing number of applications in which sensors provide probabilistic process information.
Copyright © 2021 for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). Such algorithm typically offers, as a last stage before decision making, a probability distribution over a space of alternatives. The probabilistic information can be utilized to quantify the uncertainty associated with event data, and propagate it to the log to create a stochastic, rather than deterministic, log.
To motivate the problem, consider video cameras as a data source and food preparation as the process domain. Accordingly, think about a restaurant kitchen that is monitored by video cameras. The cook, who prepares drinks and foods, works according to recipes (i.e., process models). We note, in passing, that there are multiple supervised food preparation datasets that can be used for process mining research such as, University of Dundee 50 Salads (50Salads) and the Georgia Tech Egocentric Activities (GTEA). Given a known (or discovered) set of models (e.g., cookbook recipes or historical supervised datasets), we wish to automatically identify, based on video clips, a prepared dish (e.g., Figure 1). Such identification can serve various purposes including conformance of a dish preparation with its recipe, informing diners regarding expected dish arrival time or performance improvement by identification of bottlenecks in the kitchen.
The challenge follows from the fact that the predicted trace, which is the result of data processing and learning techniques, is probabilistic (e.g., a softmax layer of a neural network). The matrix below represents a stochastic trace prediction for 12 events (e1;:::;e12) and n possible activity classes (a1;:::;an): Assuming a complementary background activity, then for all events j, we can generate a probability space such that Pn
i=1pi;j = 1: In practice, we expect the problem to battle a large number of events, much larger than the number of events in the toy datasets (e.g., 12 for Figure 1). The number of events depends on the length of the overall process and the sampling resolution, which may result in a large number of video frames. Also, whenever sampling is performed at a predetermined frequency, time points should be grouped into higher level activities. Therefore, the magnitude of the challenge can be understood by the large number of possible traces that follows from the uncertain trace representation and the fact that to date, no conformance technique was proposed to handle this type of stochastic uncertain traces.
To jump-start the discussion, we present the related literature in Section 2, followed by a taxonomy to characterise the problem dimensions (Section 3), where we also present the challenge in more details. 2 Related Literature We first review the scarce research about Process Mining (PM) with uncertain data. Then, we add context to the use-case on which we focus { video cameras { by mentioning related computer vision studies.
Data quality and uncertainty in the context of PM have been studied from
different perspectives. Several studies focused on data quality and imperfection aspects
[
Ceylan, Darwiche, and Broeck [
Research about performing PM tasks with uncertain data emerged during the last
couple of years, by a small group of researchers that included Pegoraro, Uysal, and
Aalst and their associates. Pegoraro, Uysal, and Aalst [
Computer vision literature typically refers to process discovery as `complex activity
recognition', which similarly to PM, consists of a set of sensor-detected
temporallylinked lower-level events. Thus, computer vision based process discovery is dependent
upon automatically recognizing simple activities from which the process is composed
such as `walking', `jumping', `meeting' and the temporal links between them; and
this task poses a challenge for current machine learning techniques [
In this paper, we focus on the challenge of weakly uncertain logs that were only
mentioned casually in past research [
Model (Dataset) ! Single process
Multiple processes # Observation (Log) Deterministically Known (DK) Stochastically Known (SK)
DK 1 5
SK 2 6
DK 3 7
SK 4 8
Table 1 accommodates the spectrum of conformance checking using the SK term. Case 1 is the standard conformance checking where process realizations are compared to a process model. Case 3 uses conformance for classification where several processes are given and the observation is classified to the process model with which it conforms the most. Thus, conformance checking is performed with respect to each of the known processes. Cases 5 and 7 relate to weakly uncertain observed logs. Case 5 may represent a setting in which one wants to check, for example, the conformance of a surgical procedure with its model (e.g., for educating surgeons or debriefing purposes). Such a case poses the challenge of developing a conformance technique that explicitly accommodates the probabilistic information. In such a case, an example observation may be modeled by the following probability matrix: where rows correspond to activities (e.g., a-d), columns to timestamps (e.g., e1-e4), and entries represent the probability of an activity to occur in a time point. The matrix can be the outcome of a softmax layer of a neural network; the probabilities associated with the first event e1, for example, are p(a) = 0:50;p(b) = 0:30;p(c) = 0:20, and p(d) = 0:00. We note that the presentation implicitly captures time uncertainty; for example, consider events that represent the sensor sampling time { that is, e1;e2;::: represent time moments in which probabilistic information about activities was gathered. Thus, an activity duration may be represented by a time interval between events, e.g. t(ej) t(ei); ej ei; with some probability.
In Case 7, an observed process needs to be classified into one of the process models using a conformance measure. A representative use-case may include a dataset of food preparation DK models (e.g., latte, tea, scrambled eggs, and cheese sandwich) and a SK log based on a video recorded dish preparation that needs to be automatically classified as one of the models. In such a case, we suggest conformance checking of the observation with respect to each of the models|the best conforming model is selected as the prepared dish. The challenge is to develop the conformance checking procedures for the probabilistic setting.
In Cases 2,4,6 and 8, the models are SK. Such settings may arise when creating a fully supervised dataset is too costly. A natural way to discover the models is to apply neural network techniques on videos of known dishes, which would result in a SK trace for each historical video with a deterministically known label (i.e., the dish name is known). Cases 6 and 8 in which both models and the log are SK, are the most challenging. We expect that it would be extremely hard to distinguish between two types of stochasticity. The first reflects variations across process realizations (e.g., in 60% of the realizations a ! b and in the rest a ! c) and the second type reflects quality discrepancies induced by sensors and statistical data processing techniques (e.g., the second event is b with probability of 0:6 or c with probability of 0:4).
To recapitulate, we introduced a set of challenging conformance and classification problems one needs to address when logs use uncertain data that were generated by devices, sensors and data processing algorithms. The difference with respect to related work is both in the taxonomy and the explicit way in which we model and deal with uncertainty. Modeling and solution methods will require extending conformance methods (e.g., alignments) or developing new ones based on probabilistic measures (e.g., Frobenius norm, Cross-entropy) and new cost structures.