A Deep Adversarial Model for Suffix and Remaining Time Prediction of
Event Sequences

Theis et al. [24] train a fully connected model that predicts the next event only. The experiments show an improvement over [22, 7]. The works in [17, 4] uses a Convolutional Neural Network (CNN) using image-like data structure for the next event’s label prediction task in a running process execution. The experiments show an improvement over RNN-based architectures [22, 7]. Taymouri et al. [23] propose a GAN architecture by invoking an LSTM for both the discriminator and the generator. The results showed that it outperforms previous techniques [22, 7, 2, 17] for the next activity and timestamp prediction.

Adversarial learning has received considerable attention due to its capability of generating the synthetic samples that are similar to the real one [9]. Recently GANs have been shown to be effective in improving the temporal dynamics of autoregressive models for time-series data [26]. Some works directly employ unsupervised objective by applying GANs framework to sequential data, mainly by instantiating recurrent networks for the roles of generator and discriminator. For example, Esteban et al. [6] propose Recurrent Conditional GAN (RCGAN) to produce realistic real-valued multi-dimensional time series for medical applications. The work in [14] proposes (Continuous RNN-GAN) adversarial training using LSTM networks for generator and discriminator to model the whole joint probability of a real-values sequence that can be used for music production. On the other hand, the recent work [26], combines the flexibility of the unsupervised paradigm with the supervised training for various continuous-valued time-series prediction tasks. Indeed, supervised and adversarial objectives encounter the network to adhere to the dynamics of the training data during training. Experiments show this approach outperforms baselines in predictive ability of time-series.

While these methods’ motivation is similar to ours in accounting for various temporal data prediction tasks, they consider continuous-valued time-series data. Indeed despite compelling results, little attention has been paid time-dependent events that are discrete-values.

In the proposed framework each event $e_{i}=(a_{i},t_{i})$ is shown by vector $\mathbf{e}^{(i)}=(\mathbf{a}^{(i)},t_{i})$, where $\mathbf{a}^{(i)}$ is the one-hot encoding of activity $a_{i}$. We denote the $j$-th entry of a vector by the corresponding subscript, e.g., $\mathbf{a}^{(i)}_{j}$. With such representation, an events prefix or an events suffix is shown by a sequence of vectors. For example, given $\sigma=\langle\mathbf{e}^{(1)},\mathbf{e}^{(2)},\mathbf{e}^{(3)},\mathbf{e}^{(4)}\rangle$, $\sigma_{\leq 2}=\langle\mathbf{e}^{(1)},\mathbf{e}^{(2)}\rangle$, $\sigma_{>2}=\langle\mathbf{e}^{(3)},\mathbf{e}^{(4)}\rangle$, and $\sigma_{\leq 3}=\langle\mathbf{e}^{(1)},\mathbf{e}^{(2)},\mathbf{e}^{(3)}\rangle$, $\sigma_{>3}=\langle\mathbf{e}^{(4)}\rangle$.

Since $\mathbf{e}^{(i)}$ is a vector containing representations for $e_{i}=(a_{i},t_{i})$, we define two functions $f_{a}()$ and $f_{t}()$ which extract the relevant $a_{i}$ and $t_{i}$ in $\mathbf{e}^{(i)}$. These functions can be applied to sequence of events as well, e.g., $f_{a}(\sigma_{\leq 2})=\langle a_{1},a_{2}\rangle$ and $f_{t}(\sigma_{>2})=\langle t_{3},t_{4}\rangle$.

In this part, we first provide the detail of the proposed encoder-decoder architecture and its supervised training. Next, we explain the proposed adversarial training.

The Processing block in Fig. 3 creates one-hot encoding for an activity with the highest probability. It then concatenates that vector with the corresponding predicted duration time $t_{k+1}$, which results in $\mathbf{e}^{(k+1)}$. After that, it is fed as input for the next step prediction, and thus open-loop training can be achieved.

If the ground truth activity at step $k+1$ is $\mathbf{a}^{(k+1)}_{i}$, i.e., the $i$-th entry, and the network’s prediction for such activity is $\boldsymbol{\pi}_{i}^{(k+1)}$ then the corresponding error, also known as the cross-entropy, is $L^{(k+1)}=-\mathbf{a}^{(k+1)}_{i}log\boldsymbol{\pi}_{i}^{(k+1)}$. Thus, the suffix prediction task’s loss function is the sum of such errors over all time steps until reaching [EOS]:

The adversarial training works as a minmax game between the generator and the discriminator. It starts by proposing fake and real instances. A real instance is a suffix of events in the training set, i.e., $\sigma_{>k}$, and a fake instance is formed from the generator’s output, i.e., $\hat{\sigma}_{>k}$. The training runs as a game between two players, where the generator’s goal is to maximize the quality of predictions, i.e., accurate suffix and remaining time prediction, to fool the discriminator. The discriminator’s goal is to minimize its error by evaluating the quality of generator’s predictions, see flow 4. In particular, the discriminator assigns high probability values to real instances and low probability values to fake instances. It is an adversarial game since the generator and the discriminator compete with each other, i.e., learning from the opponent’s feedback, see flows (4), (5) in Fig. 2, thus maximizing one objective function minimizes the other one and vice versa.

The discriminator can send feedback to the generator, i.e., updating the generator’s parameters via backpropagation, if its inputs are differentiable [9]; however in our work both $\sigma_{>k}$, i.e., the ground truth, and the generator’s output, i.e., $\hat{\sigma}_{>k}$, contain categorical items, i.e., activity, that have zero gradients with respect to $\theta_{g}$ and $\theta_{d}$, respectively. Thus, we get a continuous approximation to such categorical items using Gumbel-softmax distribution [10, 13]. In particular, if $\boldsymbol{\pi}^{(k+1)}$ shows the vector of probability prediction of activities for step $k+1$, see Eq. 4.1, the continuous approximation is the vector $\boldsymbol{\alpha}^{(k+1)}$, with the $i$-th entry as follow:

The Gumbel-softmax part in Fig. 2 creates event vectors $\mathbf{e}^{(i)}=(\boldsymbol{\alpha}^{(i)},t_{i})$ for the generator’s output using Eq. 4.5, and for every one-hot vector $\mathbf{a}^{(i)}$ in $\sigma_{>k}$ it forms a continuous approximation vector by placing a high probability, e.g., 0.9, on the correct activity, and $(1-0.9)/(m-1)$ on the remaining activities, where $m$ is the number of activities.

In the minmax game, we want the $G$’s output, i.e., $\hat{\sigma}_{>k}$, to be as close as possible to ground truth $\sigma_{>k}$, such that, $D$ gets confused in discriminating the mentioned suffixes of events. Formally, for a pair $(\sigma_{\leq k},\sigma_{>k}))$ and the prediction $G(\sigma_{\leq k})=\hat{\sigma}_{>k}$, we consider the following adversarial loss functions for the discriminator and the generator:

The proposed adversarial training which we call Maximum Likelihood Min-Max Estimation (MLMME) is shown in Alg. 1. For each pair of prefix and suffix $(\sigma_{\leq k},\sigma_{>k})$ in the training set $\mathcal{S}$, we update the parameters of the discriminator and the generator according to Eq. 4.6. Also, the generator’s parameters are further updated using Eq. 4.4, i.e., supervised loss. Note that, unlike original GAN [9], which needs Nash equilibrium to stop training, we consider a specific number of iterations in Alg. 1. Indeed, the objective of Eq. 4.6 is to help the supervised training to boost the generator’s performance in learning joint temporal dynamics of events across time to advance suffix and remaining time prediction. After training, we disconnect the discriminator and use the generator for the prediction tasks.

After training and during inference, the suffix and remaining time prediction proceeds one step at a time. At each step, we predict one output, i.e., the activity $a_{i}$, and its duration time $t_{i}$, see Fig. 3. We first compute a probability distribution over all activities using Eq. 4.1. We then pick the most likely activity and move to the next prediction step. This process is 1-best greedy search and makes us vulnerable to the so-called Garden-Path problem [19]. In that case, the best predicted suffix consists initially of less probable activities, which are redeemed by subsequent activities in the output sequence.

To alleviate this issue, when predicting the first activity of the decoder output, we keep a beam of the top $n$, called beam size, most likely activity choices. They are scored by their probability. Then, we use each of these activities in the beam in the conditioning context for the next activity. Due to this conditioning, we make different predictions for each. We now multiply the score for the partial prediction, and the probabilities from its activity predictions. We select the highest scoring activity pairs for the next time step. This process continues. At each time step, we accumulate the output activity probabilities, giving us scores for each partial prediction. A prediction is complete when the end of sequence token, i.e., [EOS], is produced. At this point, we remove the completed prediction, i.e., $\hat{\sigma}_{>k}$, from the beam and reduce beam size by 1. Search terminates, when no partial predictions are left in the beam.

A Beam search with size $n$, returns the $n$ most probable suffix predictions for an input event prefix among those explored in the search process. The time and space complexities of Beam search with beam size $n$ are $\mathcal{O}(nb)$ and $\mathcal{O}(n)$, respectively, where $b$ is the branching factor or the number of activities in our work.

We evaluate the performance of the proposed technique for suffix and remaining time prediction on four real-life datasets that are publicly available. No prepossessing are applied to datasets. All detests were used in baselines [22, 23, 12]. Table 1 shows some characteristics of the datasets. For each dataset, #Sequence shows the number of sequences, i.e., process executions, #Events is the number of events, #Activity represents the number of unique activities, Sequence-Length provides the length of shortest and longest sequences, and the last column shows the average and maximum cycle time, i.e., the time from starting a process execution until it ends. In details:

• •

  Helpdesk:²²2https://data.4tu.nl/articles/dataset/Dataset_belonging_to_the_help_desk_log_of_an_Italian_Company/12675977 It contains sequences from a ticketing management process of the help desk of an Italian software company. All traces start with the insertion of a new ticket into the ticketing management system. Each case ends when the issue is resolved and the ticket is closed in management system.

• •

  BPI12³³3https://data.4tu.nl/articles/dataset/BPI_Challenge_2012/12689204: It contains sequences of a loan application process at a Dutch financial institute through an on-line system from 2011/10/01 to 2012/03/14. This process includes three sub-processes from which one of them is denoted as $W$ and used already in [22, 23]. As such, we extract it from this dataset, i.e., BPI12(W).

• •

  BPI17:⁴⁴4https://data.4tu.nl/articles/dataset/BPI_Challenge_2017/12696884 It contains sequences of a loan application process at the same Dutch financial institute in BPI12 but for 2016 and their subsequent handling up to February 2nd, 2017.

For each dataset, we consider temporal splitting into three sets by 7:1:2 ratio. We use the first 70% of the sequences for training, the middle 10% of sequences for validation and the remaining 20% sequences for evaluating the performance of the model after training.

The proposed approach is implemented in Python 3.7, Pytorch 1.2, and CUDA 10.1 on a Linux server using two NVIDIA P100 GPUs with 64 GB RAM. For the encoder, the decoder, and the discriminator we use a five layer LSTM with 200 neurons in each layer. In addition, the discriminator is equipped with a fully connected layer. In detail:

• •

  We consider 500 iterations using the proposed adversarial training, i.e., MLMME. To speed-up the training convergence, we used a probabilistic teacher forcing ratio of 0.1, which accordingly allows the decoder to use the ground truth from a prior time step as input [8];

• •

  For each dataset, i.e., event log, a training instance is a pair of prefix and suffix events $(\sigma_{\leq k},\sigma_{>k}))$, where the prefix length, i.e., $k$, is equal to or greater than 2;

• •

  We apply early stopping if we observe no more improvement on the validation set for 30 iterations;

• •

  We use RMSprop as an optimization algorithm for the proposed framework with learning rate ${5e-5}$. To avoid gradient explosion, we clip the gradient norm of each layer to 1; and

• •

  We exponentially anneal the temperature $\tau$ of the Gumbel-Softmax distribution from 0.9 to 0 in Eq. 4.5 to stabilize the training.

We first discuss the results on the two prediction tasks in terms of accuracy. Next, we study the effects of adversarial training on the results. Finally, we discuss the time complexity of the approach.