Adversarial System Variant Approximation to Quantify Process Model Generalization
Julian Theis Houshang Darabi
cs.AI cs.LG I.2; H.1




































































Adversarial System Variant Approximation to Quantify Process Model Generalization
    Julian Theis, Graduate Student Member, IEEE,
        and Houshang Darabi, Senior Member, IEEE
J. Theis and H. Darabi are with the Department
of Mechanical and Industrial Engineering, University of Illinois at Chicago, 
842 West Taylor Street, Chicago, IL 60607, United States. H. Darabi is the corresponding author. 
E-mail: {jtheis3, hdarabi}@uic.edu



    December 30, 2023
======================================================================================================================================================================================================================================================================================================================================================================












In process mining, process models are extracted from event logs using process discovery algorithms and are commonly assessed using multiple quality metrics. While the metrics that measure the relationship of an extracted process model to its event log are well-studied, quantifying the level by which a process model can describe the unobserved behavior of its underlying system falls short in the literature. In this paper, a novel deep learning-based methodology called Adversarial System Variant Approximation (AVATAR) is proposed to overcome this issue. Sequence Generative Adversarial Networks are trained on the variants contained in an event log with the intention to approximate the underlying variant distribution of the system behavior. Unobserved realistic variants are sampled either directly from the Sequence Generative Adversarial Network or by leveraging the Metropolis-Hastings algorithm. The degree by which a process model relates to its underlying unknown system behavior is then quantified based on the realistic observed and estimated unobserved variants using established process model quality metrics. Significant performance improvements in revealing realistic unobserved variants are demonstrated in a controlled experiment on 15 ground truth systems. Additionally, the proposed methodology is experimentally tested and evaluated to quantify the generalization of 60 discovered process models with respect to their systems. 



Process Mining, 
Process Models, 
Petri Nets, 
Conformance Checking, 
Generalization, 
Sequence Generative Adversarial Networks, 
Deep Learning, 
Metropolis-Hastings Algorithm, 
Variant Estimation















§ INTRODUCTION

Process mining is a comparatively young research discipline that delights itself on ever-increasing popularity with applications in multiple domains such as Healthcare <cit.>, Manufacturing <cit.>, Robotic Process Automation <cit.>, Human-Computer Interaction <cit.>, and Simulation <cit.>. Commonly, process mining techniques are leveraged to analyze a system. The system is observed during runtime and process steps are recorded sequentially. Recordings are then used to discover process models that are supposed to provide insights into the underlying system, i.e. to describe its behavior. An illustrative example is a complex manufacturing plant of a given product. Such a system usually requires machines to be filled with raw materials, components to be moved and assembled, and final products to be placed on pallets. Examples of corresponding observable process steps are conveyor start, start filling pallet, stop assembling, or stop machine. In this case, the sequences of steps are recorded and used to develop a process model that describes the behavior of the manufacturing plant.

In process mining, four metrics are used to assess the quality of discovered process models: fitness, precision, simplicity, and generalization <cit.>. The first three metrics have received a lot of attention in the literature over the last decade. However, generalization is a comparatively new and fairly untouched metric. Dongen et al. <cit.> describe generalization as how well the model explains unobserved system behavior. Similarly, Syring et al. <cit.> describe generalization as a metric that is concerned with quantifying how well a process model generalizes to behavior that is possible in the (...) process but was never observed. It is obvious that assessing the generalization metric is difficult since unobserved behavior is naturally unknown. 

Process models are used to draw conclusions about the underlying system and future behavior <cit.>. Generalization, as an assessment metric, cannot be ignored in evaluating process models, because a process model that is solely evaluated on fitness, precision, and simplicity metrics might represent the observed recordings only <cit.>, and hence overfits. Such a process model is inappropriate to derive conclusions about the system behavior. Recent research studies <cit.>  have shown that state-of-the-art methods fail in assessing the extent to which a process model generalizes unobserved behavior. Hence, the measurement of generalization remains unsolved.

This paper addresses the problem of quantifying generalization by utilizing Generative Adversarial Networks (GANs) <cit.>. GANs approximate data distributions from a given sample dataset. GANs have been extensively applied in the field of computer vision  <cit.>, and are capable of learning true underlying distributions of data <cit.>. 

This paper is one of the first in applying GANs in the context of process mining by proposing and statistically testing a novel methodology to overcome the difficulty of assessing the quality metric of generalization. In particular, a Sequence Generative Adversarial Network (SGAN) is proposed to obtain a neural network that approximates the underlying system behavior. This neural network is trained on observed behavior only and is used to reveal the system's unobserved behavior. The generalization quality can then be assessed by comparing the unobserved behavior modeled by the process model with the unobserved behavior modeled by the neural network. The approach is called Adversarial System Variant Approximation (AVATAR). The effectiveness of the proposed methodology is evaluated and statistically tested in a controlled experiment utilizing 15 systems. 

The paper is structured as follows. The related work is discussed in Section <ref>. The fundamental preliminaries are provided in Section <ref> followed by the proposed AVATAR methodology in Section <ref>. An experimental evaluation using 15 ground truth systems and comprehensive result interpretations are reported in Section <ref>. Finally, Section <ref> concludes the paper and provides future research directions. A notations overview and further detailed results can be found in the Appendix.



§ RELATED WORK

The importance of generalization, i.e. measuring how well a process model represents the underlying system, is well-known <cit.>. This stems from the difficulty of deriving the unknown system from a observation sample of limited size. To date, only a few approaches measuring generalization have been proposed.

Van der Aalst et al. <cit.> suggested a method which is based on trace alignments. The measure builds on the probability of observing a new path when visiting the same process state the next time. When the average probability is low, the generalization is assumed to be high. However, this metric ignores whether a generated path is realistic, but focuses on the structural properties of the process model. Thus, this approach does not provide insights into the actual underlying system.

Buijs et al. <cit.> developed a measurement that assumes that a process model is likely to represent the underlying system if all parts of the model are frequently used. The method quantifies how often certain parts of a model are used when replaying an event log. Similar to <cit.>, this method does not consider if unseen but replayable behavior is likely to be realistic and focuses on structural assumptions only. Therefore, it fails to measure the extent to which a process model represents the behavior of the system.

A further approach has been proposed by vanden Broucke et al. <cit.> utilizing artificial negative events. This method, which is called Negative Event Generalization, is based on allowed and disallowed generalizations that can be replayed by a process model. Therefore, generalized events refer to process steps that were not recorded in a log and not considered as negative events in a given context. Such events are presumably realistic system events. However, negative events are generated using an algorithm that checks if certain negative events do occur and were preceded with a similar execution history observed in the log. Hence, this method does not generalize unobserved behavior to full extent by allowing comparatively small variations of the recordings in the event log.

Similarly, van Dongen et al. introduced an approach that is based on anti-alignments <cit.>. Anti-alignments are alignments that significantly differ from realistic ones. It is assumed that a likely possible behavior is directly reasoned by measuring the distance to anti-alignments. Therefore, process models that add new behavior without introducing new states are preferred and considered well-generalizing. However, this method ignores whether a behavior has not been observed in an event log <cit.>.

To accurately argue how well a process model generalizes, full knowledge about the underlying system must be given. Hence, the existence of a system model in a controlled experiment is assumed such that synthetic event logs can be generated <cit.>. Measuring generalization can then be reduced to the similarity between discovered process models and the system model <cit.> using standard notations. Jannsenswillen and Depaire <cit.> concluded that none of the existing methods do reliably measure generalization as required. A similar outcome is reported in <cit.>. This shows the importance of this paper that develops a novel generalization approach by approximating the system model from an event log. The proposed AVATAR methodology leverages the properties of GANs which can theoretically unveil underlying true data distribution <cit.>. 



§ PRELIMINARIES



 §.§ Logs

The subsequent definitions are partially based on <cit.>. Let S be a system. An event a ∈𝒜 is an instantaneous change of the state of S where 𝒜 is the finite set of all possible events. The cardinality of 𝒜 is denoted by |𝒜| which corresponds to the size of the set. During the system runtime, an event can occur multiple times. For every occurrence of an event, an event instance E is recorded which is a vector with at least two elements: the label of the corresponding event and the timestamp of occurrence. Consequently, e_1 is the first element of the vector E and denotes the label of the recorded event. Further optional elements of an event instance, called metadata, can be other event attributes, such as resources, people, costs, etc. In this work, only the mandatory elements of event instances are utilized. Since events are instantaneous and the point probabilities in continuous probability distributions are zero, two event instance's timestamps cannot be equal. 

A trace c ∈𝒞 is a finite and chronologically ordered sequence of event instances where 𝒞 is the infinite set of all possible traces. Let γ(c) be a function that returns the number of event instances of c, i.e. its length. The ith event instance of c is denoted by c^i.

A variant v ∈𝒱 is a sequence of events where 𝒱 refers to the infinite set of variants. Let ω: 𝒞𝒱 be a function which maps traces to variants such that for a given c its variant satisfies the subsequent condition.

    ∀_1 ≤ i ≤γ(c):v^i = c^i_1


An event log ℒ is a set of traces ℒ⊆𝒞. A variant log ℒ^* is a sample of variants of size |ℒ| and defined such that ∀_c ∈ℒ: ω(c) ∈ℒ^* and ∀_v ∈ℒ^*∃_c ∈ℒ: v = ω(c). Furthermore, a unique variant log ℒ^+ is the set of variants contained in ℒ^*, i.e. ∀_v ∈ℒ^* : v  ∃! ℒ^+. The set of all variants of S is denoted by 𝒱_S.

Let R be a random variable of S that takes on variants v ∈𝒱 and follows a probability density denoted by ℙ. When observing S and recording an event log for an infinite period of time t ∞, the relative frequency of each v ∈ℒ^* will follow ℙ.



 §.§ Petri Net

A Petri net (PN) is a mathematical modeling technique. It is commonly used to represent process models. A PN can be visualized as a directed graph in which nodes correspond to places and transitions. Each place can hold tokens which define the state of the PN. Tokens move from one place to another by executing transitions. Such transitions correspond to events of a system. This paper refers to <cit.> for formal PN introductions and definitions. 
A PN is at any given time in a certain state defined by its tokens, called a marking. Variants can be simulated by moving from one marking of the PN to another which is called playout. The set of variants that a PN can play out is denoted by 𝒱_PN. PN process models can be algorithmically extracted from an event log. Such an extraction is called Process Discovery. Two relevant state-of-the-art process discovery algorithms are introduced in Section <ref>.



 §.§ Relations between Event Logs, Process Models, and a System

Given a PN discovered from ℒ that has been recorded over a finite time t, its corresponding ℒ^+ can be related to S and PN <cit.>. ℒ^+ is understood as the observed realistic variants such that ℒ^+ ⊆𝒱_S. Consequently, there might exist a subset of realistic variants that have not been observed, denoted by 𝒱_u, such that 𝒱_S = (ℒ^+ ∪𝒱_u) and (ℒ^+ ∩𝒱_u) = ∅. 
A PN extracted from ℒ models a set of variants denoted by 𝒱_PN and is supposed to approximate 𝒱_S. Therefore, 𝒱_PN is an approximator of the system variant set denoted by 𝒱̂_S. All variant sets can be related using the Venn diagram shown in Figure <ref>. The Venn diagram illustrates the overlaps between all possible variant sets: the observed realistic variants ℒ^+ from ℒ, the realistic unobserved ones, i.e. 𝒱_u that correspond to the variants of S that have not been recorded in ℒ^*, and the set of variants that are modeled using a PN, i.e. 𝒱_PN. Each enumerated area can be described as follows:


  
  * Unrealistic and unmodeled variants (ℒ^+ ∪𝒱_u∪𝒱_PN)^∁

  This area of the Venn diagram contains all variants that are neither modeled nor realistic. 
  
  
  * Observed and unmodeled variants (ℒ^+ ∩𝒱_PN^∁)

  This area represents all realistic variants that are observed in ℒ^*, but are not contained in 𝒱_PN.
  
  
  * Unobserved and unmodeled variants (𝒱_u∩𝒱_PN^∁)

  This area corresponds to all realistic variants that have not been observed in ℒ and are not contained in 𝒱_PN.
  
  
  * Unrealistic and modeled variants (𝒱_PN∩ (ℒ^+∁∪𝒱_u^∁))

  This area represents the variants that PN models but are not realistic.
  
  
  * Modeled and observed variants (ℒ^+ ∩𝒱_PN)

  This area equals to the realistic variants that have been observed and are modeled by PN. 
  
  
  * Modeled and unobserved variants (𝒱_u∩𝒱_PN)

  This area corresponds to the unobserved realistic variants that are modeled by PN.






 §.§ Model-Log and Model-System Similarity

The similarity between a PN and a ℒ can be measured using two functions <cit.>, as stated in Definition <ref> and <ref>.


Log fitness is a function fit^ℒ : ℒ× PN  [0,1] that measures how much of the observed traces in ℒ is modeled by the PN. Based on  Figure <ref>, this is a quantification of the modeled and observed variants (ℒ^+ ∩𝒱_PN) w.r.t. to ℒ^+.



Log precision is a function prec^ℒ : ℒ× PN  [0,1] that quantifies the unobserved traces that are not contained in ℒ, but modeled by the PN. Based on Figure <ref>, this refers to a measure that quantifies the modeled and unobserved variants (ℒ^+∁∩𝒱_PN) w.r.t. to ℒ^+.


Based on the above definitions, a PN reflects ℒ perfectly if both, fit^ℒ and prec^ℒ, equal to 1. Similarly, PN can be associated to S using two functions <cit.>, as introduced in Definitions <ref> and <ref>.

System fitness is a function fit^S : S × PN  [0,1] that measures how much of the realistic variants is modeled by the PN. Based on Figure <ref>, this is a quantification of the modeled and realistic variants (𝒱_S ∩𝒱_PN) w.r.t. to 𝒱_S.



System precision is a function prec^S : S × PN  [0,1] that quantifies how much of the unrealistic variants is modeled by the PN. Based on Figure <ref>, this refers to a measure that quantifies the modeled and unrealistic variants (𝒱_PN∩𝒱_S^∁) w.r.t. to 𝒱_S.


Since the underlying system is commonly unknown, it is challenging to assess fit^S and prec^S. Generalization metrics are supposed to measure the extent to which a process model reflects the underlying system by considering the PN and ℒ. 


Generalization is a function gen : ℒ× PN  [0,1] that quantifies modeled and observed variants (ℒ^+ ∩𝒱_PN), modeled and unobserved variants (𝒱_u∩𝒱_PN), and unrealistic and modeled variants (𝒱_PN∩𝒱_S^∁) w.r.t. (ℒ^+ ∪𝒱_u).


For further illustration, the Venn diagram in Figure <ref> visualizes an averagely generalizing PN since the model allows for comparatively many unrealistic variants (area four) while allowing only partially realistic variants (area five and six). Measuring the quality metrics of fitness, precision, and generalization is also referred to as conformance checking <cit.>.



 §.§ Process Discovery Algorithms

In this manuscript, two methods to automatically discover a PN from ℒ are of interest. Both demonstrate state-of-the-art performance in recent benchmark evaluations <cit.>.

The first method is Split Miner (SM) <cit.> which is a process discovery technique that guarantees sound labeled PNs <cit.>. Its objective is the discovery of process models with high fit^ℒ and prec^ℒ scores while keeping the structure as simple as possible. To control the discovery process, SM exposes two hyperparameters with a range of [0,1]: a frequency threshold ε_1 that controls the filtering process, and ε_2 that manages the detection of parallelism.

The second process discovery technique is the Fodina (FO) algorithm <cit.>. It is an extension of the Heuristics Miner <cit.> with a comparatively higher robustness against noisy data, the capability of duplicate event detection, and an increased configuration option flexibility. The method exposes multiple hyperparameters, three of which having a high impact on the quality of the discovered model: a dependency threshold η_1, a length-one-loops threshold η_2, and a length-two-loops threshold η_3. Each one is defined in the range [0,1]. 



 §.§ Generative Adversarial Networks

A GAN consists of two neural networks, a generator G and a discriminator D, that form a minimax game to optimize each other <cit.>. G is trained to generate realistic samples of a given datatype by modeling a target distribution ℚ from samples of a random noise distribution ℤ. D is trained to differentiate between generated and given realistic samples while directing ℚ towards the underlying true data distribution ℙ. The standard loss functions to optimize G and D are defined in Equations <ref> and <ref> where 𝐄 corresponds to the expected value. 

    L_G = 𝐄_z∼ℤ[1-D(G(z))].


    L_D = 𝐄_x_r∼ℙ[1-D(x_r)] + 𝐄_z∼ℤ[D(G(z))].




  §.§.§ Sequence GANs

A special type of GAN is the Sequence GAN (SGAN) in which the  architecture of G is designed to generate samples of discrete sequences. Its main applications are found within the domain of natural language generation. This paper focuses specifically on an SGAN architecture entitled Relational GANs for Text Generation <cit.> (RelGAN) due to its superior performance in natural language generation compared to the body of existing state-of-the-art SGAN architectures described in <cit.>.



  §.§.§ RelGAN

RelGAN combines three distinct characteristics compared to existing SGAN architectures. First, it does not leverage an LSTM-based generator contrary to its sequential intuition due to apparent drawbacks <cit.>. Second, RelGAN implements a relational memory-based generator G <cit.> for better sample quality. Third, it employs relativistic loss functions for improved training of G and D.

The core concept of a relational memory is to compartmentalize information and learn to compute interactions between them <cit.>. This is achieved with a memory matrix M where each row corresponds to a memory slot. Interactions between those slots are computed using the self-attention mechanism <cit.>. Each row of the memory M_t at time t contains a compartmentalized piece of information. With H heads, there are H sets of queries, keys, and values that are calculated through three linear transformations, respectively. 

For every head, one obtains a query Q_t^h = M_tW_q^h, keys K_t^h = M_tW_k^h, and values Y_t^h = M_tW_y^h where W_q, W_k, and W_y are row-wise shared weight matrices for the queries, keys, and values, respectively. Intuitively, a query refers to the information one is looking for, the key indicates the relevance to the query, and the value is the actual content of the input. The updated memory M_t+1 is calculated by

    M_t+1 =    [M_t+1^1: ... : M_t+1^H] 
    
            M_t+1^h =    σ(M_tW_q^h([M_t;x_t]W_k^h)^T /√(d_k)) [M_t;x_t]W_y^h
 where σ(·) denotes the softmax function which is performed on each row, d_k is the column dimension of the key K_t^h, [:] denotes the column-wise and [;] the row-wise concatenation, respectively, and x_t corresponds to a new observation at time t. As reported in <cit.>, the next memory M_t+1 and output logits o_t of the generator G at time t equal to

    M_t+1 = f_θ_1(M_t+1, M_t),   o_t = f_θ_2(M_t+1, M_t)

where f_θ_1 and f_θ_2 are combinations of skip connections, multi-layer perceptron, gated operations and/or pre-softmax linear transformations.

The discriminator applies the Gumbel-Softmax relaxation technique <cit.> to overcome the critical issue of training GANs with discrete data and exposes a tunable parameter called inverse temperature denoted by β that controls the tradeoff between sample diversity and sample quality. Furthermore, the discriminator learns multiple embedded representations for each sample that is independently passed through a convolutional neural network classifier to obtain a classification score. The output of the discriminator is the mean of each embedded representation score, estimating the probability that given training samples are more realistic than generated ones. The approach stems from the argument that D(x_r) should decrease as  D(G(z))  increases <cit.>. D_r denotes a discriminator that is trained with a relativistic objective. The corresponding loss function is defined in Equation <ref>.

    L_D_r = -𝐄_(x_r,x_g)∼ (ℙ,ℚ)[log(ϕ(D_r(x_r) - D_r(x_g))]


The generator G is trained similarly by minimizing the loss function described by Equation <ref> where ϕ refers to the sigmoid function <cit.>. 

    L_G = -𝐄_(x_r,x_g)∼ (ℙ,ℚ)[log(ϕ(D_r(x_g) - D_r(x_r))]




 §.§ Metropolis-Hastings Algorithm

The Metropolis-Hastings (MH) algorithm <cit.> can generate sequences of random samples which follow a desired distribution. It is a useful technique to sample from a supposedly complex distribution, i.e. a target distribution such as ℙ. The underlying concept of the MH algorithm relies on a Markov chain <cit.> with a stationary distribution equaling to ℙ. Thus, the objective is to construct a Markov chain with transition probabilities p(x,y), where p(x,y) is the probability of moving from state x to y, such that the Markov chain equals to ℙ in the long run. 
The algorithm requires a transition kernel ℕ, which is a continuous distribution, to move randomly in space to y given a current position x, i.e. ℕ(y|x) is a density on y. Consequently, ∫_xℕ(y|x)dy = 1. ℕ is called the proposal distribution.
The underlying Markov chain is initialized as X_1 = x_1. For any t = 1, 2, 3, ..., one samples y from ℕ(y|x_t) where y is understood as a proposed value for x_t+1. The acceptance probability is calculated by

    α(x_t,y) = min(1, ℙ(y)ℕ(x_t|y)/ℙ(x_t)ℕ(y|x_t))

with which the proposed sample is accepted, i.e. x_t+1 = y. If a sample is rejected, then x_t+1 = x_t.

As elaborated in <cit.>, α(x_t, y) can be computed with the ratio of probability densities p_D_p/p_G which is available from the output of the standard discriminator D_p of a GAN. By generating one sample per Markov chain, the MH algorithm can be leveraged to produce iid samples, i.e. ℕ(y|x) = ℕ(y). Consequently, α(x_t, y) can be calculated as 

    α(x_t,y) = min(1, D_p(x_t)^-1 - 1/D_p(y)^-1 - 1)

where D_p(x) = p_D_p(x)/p_D_p(x) + p_G(x). A hyperparameter κ defines the length of the Markov chain. For a perfect discriminator and as κ∞, this recovers the distribution ℙ. 



§ METHODOLOGY

This section proposes a methodology called AVATAR to measure the generalization of a PN by approximating 𝒱_S using SGANs. Figure <ref> provides an overview.
  



 §.§ Objective

Based on the definitions in Section <ref> and the motivation, it is of interest to measure the generalization of a PN discovered by ℒ. However, quantifying the generalization is non-trivial since 𝒱_u is naturally unknown. The only information about S is a sample from ℙ in the form of ℒ over a finite time t. Recent methods aim on quantifying generalization by investigating structural properties of a PN and/or making (probabilistic) assumptions about potential unobserved realistic variants using ℒ. However, this paper follows a different and novel approach leveraging the concept of GANs to address the existing issues. The objective is to approximate 𝒱_S, and therefore 𝒱_u, by estimating ℙ from ℒ using SGANs. In this way, 𝒱̂_S can be utilized to ultimately quantify the generalization of a PN that was discovered from ℒ.



 §.§ Relating SGANs to Process Models

When discovering a PN from ℒ, state-of-the-art process discovery algorithms consider solely the temporally ordered sequence of event labels, i.e. ℒ^* of ℒ. Ideally, the discovered PN is capable of playing out variants such that 𝒱_PN = 𝒱_S. If the two sets are equal, the PN is considered perfectly generalizing. Due to the playout property, PNs are considered generative models since they can generate variants beyond ℒ^*. Conceptually, this is relatable to a generator of an SGAN which is trained to generate sequences of discrete elements beyond the training set. As such, a PN is theoretically replaceable with a neural network G: 𝒱_PN≈𝒱_G where 𝒱_G is the set of variants that G can simulate. In this paper, the objective of G is to generate variants such that 𝒱_G≈𝒱_S, since the intention of a discovered PN is to model S. 𝒱_G and 𝒱_PN are both estimators of the variant set of S, i.e. 𝒱̂_S.

GANs and SGANs have shown impressive results in generalizing underlying data distributions. AVATAR uses these advances to find a neural network model, specifically a parametrized SGAN, that estimates 𝒱_S to measure generalization. In other words, an SGAN discovers ideally the real variants of S when trained on a sample. Assuming 𝒱_G≈𝒱_S, the generalization of a PN is quantifiable by measuring the similarity between 𝒱_PN and 𝒱_G.

Given S where its R follows ℙ and given a sufficiently large sample of variants, the SGAN's generator and discriminator are optimized such that the probability density of R is estimated as ℚ where ℚ≈ℙ. In the context of process mining, the required sample to train the SGAN equals ℒ^* which is a set of realistic variants that were observed over finite time. As explained in the following paragraphs, the methodology requires an SGAN with a generator G and two discriminators: a relativistic and a standard one, denoted by D_r and D_p, respectively. Specifically, the standard RelGAN architecture is utilized and extended with a second discriminator. Hereinafter, each SGAN component is related to process mining and the suitability for estimating the unobserved system variants is elaborated to ultimately measure the generalization of a PN. 



  §.§.§ Generating Variants

G is a neural network that generates sequences of events, i.e. variants denoted by v, from random noise inputs z ∼ℤ. 
The function in Equation <ref> returns the maximum length of a trace contained in ℒ.

    μ(ℒ) = max_c ∈ℒγ(c)


It is assumed that μ(ℒ) is the maximum possible variant length of S, hence the length of v ∈𝒱_G cannot exceed μ(ℒ).

The intuition of the relational memory-based G is similar to a system that can be partitioned into smaller subprocesses. These subprocesses correspond to the "compartmentalized information" <cit.> of a relational memory. The dependencies which form the system can be referred to as the "interactions between compartmentalized information" <cit.>. Practically, this is achieved with M that is used to calculate interactions and updates. A relational memory increases the expressive power of G to generate realistic variants by implicitly identifying the subprocesses and relating their states to S. Therefore, a relational memory is suitable for modeling the potential high-modality of ℙ. These modes might range from simple logical rules such as a_2 always follows a_1 where {a_1, a_2}⊆𝒜, to complex long-run event patterns. Especially the complex long-run patterns are likely to occur with low probabilities and are consequently rarely or never recorded in ℒ.

The state of each subprocess corresponds to a row of the memory M_t at time t. These states and their interdependencies are learned using gradient-based optimization when training G. Equation <ref> illustrates that at time t, the next memory's rows and outputs, i.e. events, are combinations of multiple operations denoted by f_θ_1 and f_θ_2. This can be interpreted as a complex representation of a PN marking and transition firings. Most of the f_θ_1 and f_θ_2 operations are relatable to PNs. Skip connections can express the edges of a PN and gated operations can be inferred as split and join gateways. Firing a certain transition in a PN is equivalent to moving to a new state of S and consequently to new states of the corresponding subprocesses. Each updated row of M represents those state transitions. Thus, G learns implicitly the state transition rules of S which is similar to process discovery.



  §.§.§ Discriminating Variants

The neural network architecture of D_r led to major performance improvements in natural language generation tasks <cit.>. It is therefore uncontested to utilize D_r for discrimination between 
v ∈ℒ^* and v ∈𝒱_G.
Its main properties are directly relatable to process mining.

The hypothesis of learning multiple embeddings in D_r is that each embedded representation may capture specific aspects of an input sequence. From a process mining perspective, each embedding implicitly explicates different features that provide insight into subprocess logic or subprocess state interactions of the variant under consideration. Intuitively, a discriminator like D_r that analyzes an input variant from multiple perspectives provides a more comprehensive guiding signal to train G compared to single embedding architectures <cit.>.

Relativistic loss functions lead to significant performance improvements across different GAN applications, including SGANs. Hence, a relativistic discriminator and generator is preferred to increase the quality of G. However, relativistic discriminators are inapplicable to increase the sampling quality using the MH algorithm due to the unavailability of the probability density of an input to be realistic or fake, i.e. p_D_p/p_G. To leverage both properties, the RelGAN architecture is extended with a second discriminator, denoted by D_p. The architectures of both discriminator neural networks are identical, but they are trained with different loss functions. D_r optimizes the relativistic loss described in Equation <ref> whereas D_p is based on the standard loss by maximizing the probability of correctly classifying observed and generated variants, as described in Equation <ref>. By extending a RelGAN with a second discriminator, the MH algorithm is applicable to increase the sampling quality, as described in Section <ref>. 



 §.§ Postprocessing

Sometimes, GANs appear successfully optimized, but ℚ is still far from ℙ <cit.>. Turner et al. <cit.> developed an approach to overcome this issue on image GANs, as described in Section <ref>. The AVATAR approach transfers the idea from image GANs to process mining SGANs.

By applying the MH algorithm on top of a trained SGAN that generates variants, the likelihood of sampling realistic variants from ℙ can be increased, as experiments show in Section <ref>. Theoretically, a threshold-based filtering of variants generated by PN is realizable without an SGAN, too. However, a threshold value and the likelihood of realistic variants is then only determinable on ℒ and the structure of PN. This goes back to existing generalization measures, as introduced in Section <ref>. In comparison, when leveraging the MH algorithm on an SGAN, generated variants are evaluated using inferred knowledge beyond ℒ. This stems from the hypothesis that G and D learn characteristics of ℙ. Thus, it is assumable that the MH algorithm can improve the performance of sampling realistic variants contained in 𝒱_S.



 §.§ Sampling the Unobserved

Discovering 𝒱_u is achieved following two sampling methodologies: naively sampling from G and by utilizing the MH algorithm, denoted by GAN_β and MHGAN_β, respectively.

Given a trained G that approximates ℙ, variants can be sampled naively from its estimated distribution ℚ. When sampling k times, n unique variants are observed such that n ≤ k. The chart of the ordered relative frequencies for each v follows an exponential distribution. When k is a large value, the sorted relative frequency chart of the n unique variants approximates this property. Intuitively, the variants with a high relative frequency are of interest since those are the ones that are modeled confidently by G. Consistently, variants with a low relative frequency are modeled with less confidence and are therefore likely to be unrealistic. Thus, the value of k must be reasonably determined during the sampling stage. The union of the sampled n unique variants and ℒ^+ form  𝒱̂_S. Consequently, 𝒱̂_u = (ℒ^+^∁∩𝒱̂_S) defines the approximated set of unobserved realistic variants. The pseudocode for this sampling procedure is illustrated by Algorithm <ref>.



Rather than naively sampling from G and relying on the described intuition, the MH algorithm can be utilized to estimate 𝒱̂_S. A Markov chain of length κ = 500 is proposed that is initialized with a withheld variant subset ℒ^+_e ⊆ℒ^+ to avoid the phenomenon of burn-in <cit.>. 
The sampling process terminates as soon as the number of unique generated variants converges. This is controlled using a patience hyperparameter π. More specifically, sampling terminates as soon as none of the π most recent generated variants are novel. The pseudocode for this sampling procedure is illustrated by Algorithm <ref>.







 §.§ Quantifying Generalization

Given that ℚ≈ℙ, 𝒱_u is approximable by naively sampling from G or using the MH algorithm with G and D_p.
The generalization of a PN is then quantifiable by measuring (ℒ^+ ∩𝒱_PN), (𝒱̂_u∩𝒱_PN), and  (𝒱_PN∩ (ℒ^+∁∪𝒱̂_u^∁)) w.r.t. 𝒱̂_S. The generalization of a PN is suggested to be measured using a synthetically generated event log of the estimated system variants, denoted by ℒ_S such that 
|ℒ_𝒮| = |𝒱̂_S| and ∀_c ∈ℒ_𝒮: ω(c) ∈𝒱̂_S. 
The extent to which the PN represents 𝒱̂_S is measured using 
fit^ℒ(PN, ℒ_S^*). 
Moreover, 𝒱_PN should not contain variants that are not contained in 𝒱̂_S. 
This equals to prec^ℒ(PN, ℒ_S^*). 
If 
𝒱̂_S = 𝒱_S, 
then 
fit^S = fit^ℒ(PN, ℒ_S^*)
and
prec^S = prec^ℒ(PN, ℒ_S^*). 
Since a generalization score is supposed to be a single value, the harmonic mean of fit^ℒ and prec^ℒ on PN and ℒ^*_S is proposed in Equation <ref> as a quantification of generalization. 

    gen(PN,ℒ_S^*) = 2 * fit^ℒ(PN,ℒ_S^*) * prec^ℒ(PN,ℒ_S^*)/fit^ℒ(PN,ℒ_S^*) + prec^ℒ(PN,ℒ_S^*)




§ EXPERIMENTAL EVALUATION

This section focuses on answering the following four questions to experimentally evaluate the proposed approach.

Q1: Does the AVATAR sampling methodology approximate the true number of system variants better than a discovered process model?

Q2: Can the AVATAR sampling methodology detect a larger proportion of system variants than a discovered process model?

Q3: Does the AVATAR sampling methodology detect a larger proportion of unobserved system variants than a discovered process model?

Q4: Does the proposed generalization quantification lead to metric values that are closer to the expected scores? 

The experimental evaluation is based on ground truth systems that are introduced in Section <ref> along with the required metrics in Section <ref>. Baseline scores for evaluation are established in Section <ref> using state-of-the-art process discovery and conformance checking techniques. Finally, Section <ref> investigates the performance of the proposed approach. Section <ref> provides answers to questions Q1-Q3 that are underscored by statistical tests in Section <ref>. Section <ref> provides answers to Q4. 



 §.§ Ground Truth Systems


The ground truth systems on which the evaluation of AVATAR is based, are 15 artificial PNs that have been explained in <cit.> and are publicly available[ https://github.com/gertjanssenswillen/processquality/]. These models were created based on a system generation algorithm, as described in <cit.>. The method allows different input parameters, such as the distribution for the number of leaf nodes, the distribution for the type of operator nodes, and the probability for silent and duplicate events <cit.> to control the structure of the resulting PN. The 15 ground truth systems are classified as either moderate complex or highly complex <cit.>, based on the findings in <cit.>. Process discovery algorithms perform differently when system behavior is complex, such as in real-life applications, compared to more elementary behavior, such as in artificial setups. Therefore, the ground truth systems that are classified as moderate complex outline fewer leaf nodes and a smaller proportion of advanced constructs, such as loops and inclusive choices, compared to high complex PNs.

An overview of the systems and their variants can be found in Table <ref>. Playout is performed on each ground truth system to obtain 𝒱_S. Loops in each PN structure are controlled such that every place can produce a maximum of three tokens. Hence 𝒱_S is finite. 𝒱_S is randomly split into two mutually exclusive sets ℒ^+ and 𝒱_u. ℒ^+ contains 70% of the variants including at least one variant where its size equals the maximum length of the system. 𝒱_u contains the remaining 30% of variants. For every S, ℒ is generated such that |ℒ| = |ℒ^+| and ∀_c ∈ℒ: ω(c) ∈ℒ^+.





 §.§ Metrics

Several different metrics are utilized to evaluate the extent to which discovered PNs and SGANs model 𝒱_S. tp refers to the true positive rate, i.e. the ratio of the number of realistic variants over the number of generated variants where 𝒱̂_S can be either the result of PN playout or sampling via GAN_β or MHGAN_β. Consequently, the false positive rate is the ratio of the number of unrealistic variants over the number of generated variants, fp = 1 - tp. Furthermore, the ratio of the number of generated realistic variants over the number of realistic variants, the ratio of the number of generated realistic variants over the number of observed variants, and the ratio of the number of generated unobserved and realistic variants over the number of unobserved variants are measured and denoted by tp_S, tp_o, and tp_u, respectively. Furthermore, when holding out variants from ℒ^+, such as ℒ^+_e, the ratio of the number of generated realistic variants over the number of holdout variants is calculated as tp_e.

    tp_S = |𝒱̂_S ∩𝒱_S|/|𝒱_S|,   tp_o = |𝒱̂_S ∩ℒ^+|/|ℒ^+|
    
        tp_u = |𝒱̂_S ∩𝒱_u|/|𝒱_u|,   tp_e = |𝒱̂_S ∩ℒ^+_e|/|ℒ^+_e|




 §.§ Process Discovery and Conformance Checking

This subsection introduces the experimental setup of discovering process models from the ground truth systems and checking their conformance to establish a baseline.



  §.§.§ Setup

SM and FO are used to discover PNs from ℒ for each of the 15 ground truth systems. Hyperparameter optimization is performed to discover high quality process models. For each of the 15 ground truth system, 121 PNs are discovered using SM with unique ε_1 and ε_2 pairs and parameter interval steps of 0.1, and 216 PNs using FO with unique η_1, η_2, and η_3 combinations and parameter interval steps of 0.2. Two process models per process discovery algorithm and ground truth system are selected by performing conformance checking using existing metrics. The process model which resulted in the highest generalization score is selected for each of the process discovery algorithms SM and FO, denoted by PN_SM1 and PN_FO1, respectively. Additionally, two further process models PN_SM2 and PN_FO2 are selected which score high log fitness and generalization across the discovered process models on each ground truth system by SM and FO, respectively. The intuition is that a PN with a high log fitness and generalization score supposedly models the underlying system. It should be noted that PN_SM2 or PN_FO2 can be the same process models as PN_SM1 or PN_FO1. Finally, four ideally different hyperparameter-optimized PNs per ground truth system are used for further evaluation.

For every ground truth system, four  process models are selected. For each PN, token-based log fitness fit^ℒ_t <cit.> and the ETConformance-based log precision prec^ℒ_etc <cit.>, alignment-based log fitness fit^ℒ_a and precision prec^ℒ_a <cit.>, and generalization gen_ETM <cit.> are obtained. These conformance measures are the de-facto standard when evaluating process models. Two methods are used to evaluate log fitness and log precision since it is not guaranteed that the process discovery algorithms create sound PNs, therefore alignment-based metrics are not applicable. However, token-based conformance scores might be ambiguous <cit.> and therefore are eventually unrepresentative. Bold values refer to the metrics that have been optimized during hyperparameter determination. The reported conformance checking evaluations are performed using the Python-based open source process mining library PM4Py <cit.>.

Playout is performed for each selected PN to obtain 𝒱_PN as an estimator of 𝒱_S. When generating 𝒱_PN, the maximum variant length is set to μ(ℒ) since it is assumed that the log contains a trace which is equal to the maximum variant length of S. Based on those sets, the values for tp, fp, tp_S, tp_o, and tp_u are calculated .



  §.§.§ Results

  

This subsection reports significant observations. The Appendix contains all detailed results.

PN_SM1 and PN_FO1 of System 1 score comparatively high generalization between 0.828 and 0.845. This seems to accurately reflect the generalization of the process models since high tp ratios are obtained. Around 70% and 60% of ℒ^+ and 𝒱_u are covered by 𝒱̂_S. However, roughly 50 variants of 𝒱_S are unmodeled by the PN. Hence, the generalization score seems representative, however, the metric was not designed to measure the extent to which unobserved variants are modeled and has been proven to fail, as discussed earlier. PN_FO2 has a higher fitness, but lower precision and a low generalization score of around 56%. This value seems reasonable, too, since tp is comparatively very low. Overall, the model generalizes comparatively well and infers roughly 85% of 𝒱_u .

A generalization misalignment is observed when analyzing the models of System 2. PN_FO1 scores the highest generalization score. However, it cannot playout any realistic variant. Therefore, PN_FO1 does not generalize at all and the obtained generalization score is misleading. PN_FO2 performs with higher tp, tp_S, tp_o, and tp_u values than PN_SM1 or PN_SM2. However, the SM models score in comparison 0.13 lower which highlights the misalignment. 

The resulting scores of PN_FO1 on System 5 are questionable.
Conformance checking results in a decent token-based fitness, but very low precision. This indicates a spaghetti-like structure of the model which leads to a large |𝒱̂_S|. However, none of the variants in 𝒱̂_S are realistic. Still, this model scores the highest generalization score across the discovered PNs, though it is intuitively expected to be close to 0. 

For System 11, four PNs are discovered with comparatively high scores of generalization in the range of 0.865 and 0.915. However, this is not reflected in the ratios. Out of 415 possible realistic variants, especially the FO PNs tend to model more variants that are not realistic. This results in low tp ratios. 
When optimizing the process discovery for high generalization scores, FO discovers models with low fitness and precision scores which result in unsound PNs. Therefore, the generalization score should be rather low than high. However, PN_FO2 has a much higher fitness and precision, but still a low tp ratio. Though this model plays out more realistic variants, it results in a lower generalization score compared to PN_FO1. This phenomenon is observed with PN_SM1 and PN_SM2, too. PN_SM1 results in lower conformance checking scores except for generalization compared to PN_SM2, but generalizes worse according to the true positive ratios. Only tp is improved. 

When performing the experiment on System 12, PN_FO1 and PN_SM1 are both unsound without fitting variants. However, their generalization scores are above 90% which seems counterintuitive. Nonetheless, PN_SM1 reproduces certain observed and unobserved variants with a high fp rate. Interestingly, PN_FO2 results in the same fp rate with much higher tp_o and tp_u ratios, thus actually generalizing better than PN_SM1. However, their generalization scores are very different.

Similarly to System 12, PN_SM1 and PN_FO1 of System 14 are unsound PNs that cannot generate any realistic variant. However, their generalization score is the highest among the discovered PNs. According to the true positive ratios, PN_SM2 and PN_FO2 generalize with a high fp rate. Their generalization score is above 0.91, but their true positive ratios vary. PN_FO2 plays out significantly more variants than PN_SM2 including more realistic ones.

These results align with the conclusions of <cit.> that the generalization metric implemented in PM4Py does not reflect generalization as desired. Hence, the results emphasize the problem and justify the motivation of this paper. 




 §.§ Methodology Evaluation



  §.§.§ SGAN Training and Sampling

For each S, two extended RelGANs are trained as proposed in Section <ref>. The first one is trained with β = 100 to encourage exploration for an improved sample quality <cit.>. The second model is trained with the maximum value, β = 1000, to encourage higher sample diversity. A vanilla relational memory architecture is chosen for G due to observed superior performance over architectural variations <cit.>. Furthermore, the head size of the relational memory has been reduced from 512 to 256 since the ground truth systems are intuitively less complex than the original application domain of RelGANs. The remaining training parameters are the default values as in <cit.>.

ℒ^+ is split into a 90% train set denoted by ℒ^+_t, and a 10% holdout validation set, ℒ^+_e. First, G is pretrained with 100 epochs as described in <cit.>. Then, the extended RelGAN is trained for 5,000 adversarial epochs. To obtain 𝒱̂_S and to calculate tp_e, 10,000 variants are drawn every 20 epochs from G. The best performing model is the one leading to the highest obtained tp_e value and to a comparatively small |𝒱̂_S|. This is a widely adopted approach to train neural networks <cit.>. The determined models are then used to naively sample 10,000 variants (GAN_β=100 and GAN_β=1000) or to sample using the MH algorithm (MHGAN_β=100 and MHGAN_β=1000) to establish four estimators of 𝒱_S.

The evaluation procedures are implemented using Texygen <cit.> and Tensorflow <cit.>. The process model and event log processing methods are based on PM4Py <cit.>. The corresponding source code is publicly available[https://github.com/ProminentLab/AVATAR]. The training and sampling have been performed on NVIDIA GeForce RTX 2080 GPUs and took 2-3 hours per extended RelGAN and dataset.



  §.§.§ Sampling Results

Figure <ref> visualizes the number of sampled variants, i.e. |𝒱̂_S|, tp, and tp_u for each ground truth system and for each of the four PN and four GAN sampling approaches. The visualization of the number of generated variants show that the SGANs are generating a number of variants closer to the ground truth compared to PNs across all datasets. This is even more prominent on the highly complex systems 11-15. Therefore, the answer to Q1 is that the AVATAR sampling methodology indeed approximates the true number of system variants better than process models that are built from state-of-the-art discovery algorithms.

The middle visualization of Figure <ref> shows that for most of the systems, the tp values for the GAN sampling approaches are higher than for PNs. This is especially prominent for highly complex systems. It can be seen that for MHGAN_β=100 and MHGAN_β=1000 the tp values are increased compared to GAN_β=100 and GAN_β=1000. This indicates that w.r.t. Q2, the AVATAR sampling methodology models a higher proportion of system variants compared to the discovered process models.

The bottom graph visualizes the tp_u ratios and provides information to answer Q3. Most SGANs do not necessarily model more unobserved variants compared to PNs. Moreover, when applying the MH algorithm, tp_u values tend to decrease compared to naive GAN sampling. 

A tradeoff between the number of generated variants, tp, and tp_u exists and needs to be investigated to answer Q3. When analyzing solely tp_u on systems 7, 8, and 10, it seems that the discovered PNs model unobserved variants better than SGANs. However, the corresponding tp is lower than the tp of some SGANs. When considering tp and tp_u combined, SGANs perform significantly better compared to the discovered PNs since their fp rate is much lower. This means that the set (𝒱_PN∩ (ℒ^+∁∪𝒱_u^∁)) is comparatively smaller which is desirable. Moreover, Figure <ref> indicates that sampling with MH increases tp and decreases the number of generated variants and tp_u compared to naive GAN sampling. This means that fp is further reduced, however, at the cost of the number of unobserved realistic variants.





  §.§.§ Statistical Significance

Ultimately, a generative model is desired such that 𝒱̂_S = 𝒱_S. This means that |𝒱̂_S| should be as close as possible to |𝒱_S| and tp and tp_u are ideally equal to 1.0. Since most of the values for |𝒱̂_S| are higher than the corresponding |𝒱_S|, one can combine tp and tp_u in a single measure to investigate the tradeoff. Figure <ref> illustrates tp_u over tp scores for all PNs and SGAN sampling models in a two-dimensional space.

  

Since highly generalizing models are expected to have a high tp and tp_u score, one should find ideally as many models as possible plotted in the upper right corner of Figure <ref>. The discovered PNs generally perform with low tp rates whereas the SGANs results are found closer towards the desired upper right area of the space. To counterfeit imbalances of tp and tp_u, a score s is introduced in Equation <ref> which equals to the Euclidean distance between the origin (0,0) and a model in the two-dimensional space represented by tp and tp_u weighted by the angle between the model vector in space and the reference one pointing to (1,1). The intuition is that a model with low tp and high tp_u should not be considered better generalizing than a model with average, but balanced tp and tp_u scores. 

    s(tp, tp_u) = tp + tp_u/√(2)


One can statistically test if the mean differences of s between an SGAN sampling model and a corresponding PN are significantly higher. 16 individual statistical tests are performed with each 15 difference values comparing the playout outcomes of one PN with one SGAN sampling architecture at a time. The Shapiro-Wilk test <cit.> is an appropriate test for small sample sizes to assess if given values are normally distributed. An upper-tailed paired t-test <cit.> is performed when the Shapiro-Wilk test is passed, otherwise an upper-tailed Wilcoxon signed-rank test <cit.> assesses the mean difference. The resulting p-values are visualized in Figure <ref>. Based on a standard confidence interval of 95%, the SGAN sampling models are in all cases statistically significant. To conclude, the AVATAR sampling methodology approximates the true number of system variants better, and detects a higher proportion of system variants and a higher ratio of unobserved system variants than the discovered process models (Q1-Q3).
  



  §.§.§ Generalization

  

For each PN, the corresponding four 𝒱̂_S sets that are approximated by the SGAN models, are used to measure the generalization of the PN as introduced in Equation <ref> to answer Q4. The used fitness and precision functions are fit^ℒ_t and prec^ℒ_etc since those are the most established conformance measurement methods and some of the PNs are unsound requiring non-alignment-based metrics. However, any fitness and precision function can be used, as long as the definitions in Section <ref> apply. For each PN, four generalization scores are reported corresponding to the four 𝒱̂_S of the SGAN sampling models. The arithmetic mean of scores is supposed to represent the generalization of the PN. Figure <ref> illustrates the obtained results which are closer to the expected and desired generalization scores than the ones in Section <ref>.

Among all PNs of System 1, PN_FO2 is the worst generalizing model. This is reflected by the generalization score visualized in Figure <ref>. Similarly, PN_FO1 in System 2 is recognized as the least generalizing one which is correct since the model cannot play out any realistic variant. The AVATAR generalization scores for System 4 and 7 are all identical which confirms the earlier observations. However, as expected, the scores are lower due to the observed tp rate. This is caused by fit^ℒ_t and prec^ℒ_etc, therefore more advanced fit^ℒ and prec^ℒ functions should be considered. For System 5, both FO models are least generalizing, whereas PN_FO1 performs worse than PN_FO2. This is succesfully detected using the AVATAR methodology. 
The results for System 6 and 2 are similar. PN_FO1 is succesfully detected as the least generalizing process model. Both SM PNs result in a high tp rate and therefore in a higher generalization score. In comparison, PN_FO2 models more variants of 𝒱_u, but at the cost of a low tp, thus a lower generalization score is obtained.

For high complex systems, all PN_FO1 models are detected to be least generalizing. The best score is obtained on System 15 and PN_FO2 which is a model with a comparatively high tp and tp_u rate, therefore confirming the proposed methodology. Notably, PNs discovered on System 14 generalize worse than PNs on other systems. 

To answer Q4, the proposed methodology accurately detects relative generalization when comparing process models of the same system and detects significant sets of unobserved variants. However,  the actual scores do not provide sufficient insight into the true generalization yet. 
This is caused by the drawbacks of fit^ℒ_t and prec^ℒ_etc <cit.>. With AVATAR, quantifying generalization is reduced to accurately measure fit^ℒ and prec^ℒ. Based on the experiments, fit^ℒ_t and prec^ℒ_etc are anticipated to be replaced with more advanced methods. A future research study should address the evaluation using log fitness and log precision metrics beyond fit^ℒ_t and prec^ℒ_etc towards more precise and absolute generalization scores.



§ CONCLUSION

This paper proposed a novel methodology to quantify the generalization of PN-based process models. Rather than measuring directly the extent to which a PN represents the underlying unknown system, an SGAN is trained on an event log to obtain a set of the realistic variants of the system. The intuition relies on the objective of GANs to model an estimated distribution that converges towards the true underlying data distribution. The approach demonstrated statistical significance in unveiling unobserved realistic variants in a controlled experiment. Additionally, experiments have shown that generalization can be measured as the harmonic mean of log fitness and log precision on the estimated variant set of the system modeled by an SGAN.

In comparison to state-of-the-art methods that either try to measure the extent to which a process model generalizes the underlying system using the event log only or by interpreting structural properties of the PN, the proposed AVATAR methodology relies on a deep learning technique which has shown outstanding results in various computer vision and language modeling applications. Instead of relying solely on the observations, AVATAR approximates unobserved variants of a system by inferring knowledge beyond the event log. After revealing a set of unknown system variants, established log fitness and log precision metrics are leveraged to quantify generalization. This work demonstrates statistical significant results in obtaining unobserved variants using SGANs and succesfully detects  the relative generalization of process models. Thus, AVATAR is a step forward towards reliably measuring generalization. Besides a novel perspective on the metric of generalization, SGANs enable other real-world applications in the domain of process mining, such as for the analysis of black-box controller and software as in <cit.>, or to obtain robust and accurate simulation models.

In practice, access to the ground truth system is usually unavailable or restricted. However, to verify if newly yielded variants by AVATAR belong to the set of system variants, access to the ground truth system is required. This hinders the evaluation of the proposed approach when only real-world event logs are given. Future research needs to be conducted that focuses on the integration and verification of newly yielded variants by AVATAR into event log generation <cit.> and process model enhancement methodologies.

Further future research is anticipated to be conducted in four directions. 
First, research studies are required that focus on more advanced log fitness and log precision methods towards precise and absolute generalization measurements.
Second, SGANs are in their infancy and efficient training with guaranteed satisfactory results is cumbersome. Hence, research is desired to focus on advancing SGAN architectures for the purpose of process mining.
Third, comprehensive elaborations on the impact of the size and bias of given event logs will mature the proposed methodology.
Finally, the approach demonstrated significant results on 15 ground truth systems that were artificially created. To further underscore the significance of AVATAR, a comprehensive study on real-world systems is anticipated which might unveil further optimization possibilities.




















§ APPENDIX



 §.§ Appendix: Notations



  |·| cardinality of a set

  :, ; column- and row-wise concatenation

  a event

  𝒜 finite set of all events

  α acceptance probability in the MH algorithm

  β inverse temperature RelGAN hyperparameter  

  c trace

  𝒞 set of traces

  c^i ith event instance of a trace c

  d_K column dimension of the key K

  D discriminator neural network

  D_p discriminator trained on standard loss

  D_r discriminator trained on relativistic loss

  E event instance vector

  e_1 label of an event instance

  𝐄 expected value

  η_1 dependency threshold of FO

  η_2 length-one-loop threshold of FO

  η_3 length-two-loops threshold of FO

  ε_1 filtering hyperparameter of SM

  ε_2 parallelism hyperparameter of SM

  f_θ_1, f_θ_2 parametrized neural network functions

  fp false positive rate

  fit^ℒ log fitness

  fit^ℒ_a token-based log fitness

  fit^ℒ_t alignment-based log fitness

  fit^S system fitness

  γ(c) returns number of event instances of a trace c

  G generator neural network

  GAN_β naive SGAN-based sampling

  gen generalization

  gen_ETM ETM generalization function

  gen(PN,ℒ_S^*) proposed AVATAR generalization

  H set of heads

  h head

  k number of samples to draw per GAN_β

  κ length of Markov chain

  K key matrix

  L loss function

  L_D discriminator loss function

  L_G generator loss function

  ℒ event log

  ℒ^* variant log

  ℒ^+ unique variant log

  ℒ^+_e holdout unique variant log

  ℒ^+_t training unique variant log

  M memory matrix

  MHGAN_β SGAN-based sampling with MH algorithm

  μ(ℒ) maximum length of trace in an event log

  ℕ proposal distribution of the MH algorithm

  o_t output logit at time t

  ω(c) function mapping a trace c to its variant

  p probability density

  ℙ probability distribution

  PN Petri net process model

  prec^ℒ log precision

  prec^ℒ_a alignment-based log precision

  prec^ℒ_etc log precision

  prec^S system precision

  π MH algorithm patience hyperparameter

  ϕ sigmoid function

  ℚ probability distribution

  Q query matrix

  R random variable of S that can take on variants

  S system

  s(tp, tp_u) tradeoff function between tp and tp_u

  σ softmax function

  t time

  tp true positive rate

  tp_S true positive rate over the 𝒱_S

  tp_o true positive rate over the ℒ^+

  tp_u true positive rate over the 𝒱_u

  tp_e true positive rate over the ℒ^+_e

  v variant

  𝒱 set of variants

  𝒱_G set of variants that G generates, estimator 𝒱̂_S

  𝒱_PN set of all possible PN variants, estimator 𝒱̂_S

  𝒱_S set of all variants of a system S

  𝒱̂_S approximated set of all system variants

  𝒱_u set of all unobserved variants of a system S

  𝒱̂_u est. set of all unobserved system variants

  W weight matrix

  x_r real sample

  x_t sample at time t

  x_g generated sample

  Y values matrix

  z noise sample

  ℤ noise distribution

  x, n, y variables used in different contexts

















































IEEEtran








-2plus -1fil

[
    < g r a p h i c s >
]Julian Theis received the B.Eng. degree in Media Technology in 2014 and the M.Eng. degree with distinction in Media and Communications Technology in 2016, both from the RheinMain University of Applied Sciences, Wiesbaden, Germany. He is currently pursuing the Ph.D. degree with the Mechanical and Industrial Engineering Department, University of Illinois at Chicago. 

Before joining Prominent Laboratory, the university's foremost research facility in process mining, he was working as a software engineer for a leading company in media and workflow automation, broadcast management, and OSS software in Germany.
His research interests include process mining, its applications to industrial, IT, and business processes, and deep learning. 





[
    < g r a p h i c s >
]Houshang Darabi (S'98–A'00–M'10–SM'14) received the Ph.D. degree in industrial and systems engineering from Rutgers University, New Brunswick, NJ, USA, in 2000. 

He is currently a Professor with the Department of Mechanical and Industrial Engineering, University of Illinois at Chicago (UIC). He has been a contributing author of two books in the areas of scalable enterprise systems and reconfigurable discrete event systems. His research has been supported by several federal and private agencies, such as the National Science Foundation, the National Institute of Standard and Technology, the Department of Energy, and Motorola.  His current research interests include the application of data mining, process mining, and optimization in design and analysis of manufacturing, business, project management, and workflow management systems.


















