New Plug-in: Replay using Recomposition

A new plug-in has been added to the Divide-and-Conquer framework: The “Replay using Recomposition” plug-in. Initially, this plug-in is similar to the “Replay with Decomposition” plug-in, but it does not stop there. Where the “Replay with Decomposition” plug-in stops after having done the decomposed replay, the “Replay with Recomposition” possibly continues to improve on the result.

As mentioned in

  • [PDF] [DOI] H. M. W. Verbeek and W. M. P. v. d. Aalst, “Merging alignments for decomposed replay,” in Application and theory of Petri nets and concurrency, Torun, Poland, 2016, pp. 219-239.
    [Bibtex]
    @InProceedings{Verbeek16,
    Title = {Merging Alignments for Decomposed Replay},
    Author = {Verbeek, H. M. W and Aalst, W. M. P. v. d.},
    Booktitle = {Application and Theory of {P}etri Nets and Concurrency},
    Year = {2016},
    Address = {Torun, Poland},
    Editor = {Kordon, F and Moldt, D.},
    Month = {June},
    Pages = {219--239},
    Publisher = {Springer International Publishing},
    Series = {LNCS},
    Volume = {9698},
    Abstract = {In the area of process mining, conformance checking aims to find an optimal alignment between an event log (which captures the activities that actually have happened) and a Petri net (which describes expected or normative behavior). Optimal alignments highlight discrepancies between observed and modeled behavior. To find an optimal alignment, a potentially challenging optimization problem needs to be solved based on a predefined cost function for misalignments. Unfortunately, this may be very time consuming for larger logs and models and often intractable. A solution is to decompose the problem of finding an optimal alignment in many smaller problems that are easier to solve. Decomposition can be used to detect conformance problems in less time and provides a lower bound for the costs of an optimal alignment. Although the existing approach is able to decide whether a trace fits or not, it does not provide an overall alignment. In this paper, we provide an algorithm that is able provide such an optimal alignment from the decomposed alignments if this is possible. Otherwise, the algorithm produces a so-called pseudo-alignment that can still be used to pinpoint non-conforming parts of log and model. The approach has been implemented in ProM and tested on various real-life event logs.},
    Doi = {10.1007/978-3-319-39086-4_14},
    Url = {http://www.win.tue.nl/~hverbeek/wp-content/papercite-data/pdf/verbeek16.pdf}
    }

it is possible to merge subalignments back together into an alignment. However, this may not be possible for all subalignments, as some of them will contain conflicts on the borders of the subalignments. After merging, these subalignments are not an alignment, but a pseudo alignment.

After having done a decomposed replay that results in pseudo alignments, the “Replay with Recomposition” plug-in will do another decomposed replay, in which one of the conflicts is solved by combining the related subnets. As such, it resolves the conflict by recomposing these subnets into a single subnet.

Provided sufficient time (and resources), the “Replay with Recomposition” plug-in will return the same fitness value as the non-decomposed replay would, but possibly in less time. Furthermore, the “Replay with Recomposition” has the possibility to terminate earlier, based on some termination criteria. For example, this plug-in allows you to specify that you want to have the best possible fitness value, but that it may only take 10 minutes to compute it. This best possible fitness value will be an interval of a lower bound and an upper bound, with the guarantee that the exact fitness will be in that interval.

Input

  1. An event log
  2. An accepting Petri net

Output

  1. An alignment, possibly containing pseudo alignments.

Package

DecomposedReplayer

Description

As mentioned in

  • [PDF] [DOI] H. M. W. Verbeek and W. M. P. v. d. Aalst, “Merging alignments for decomposed replay,” in Application and theory of Petri nets and concurrency, Torun, Poland, 2016, pp. 219-239.
    [Bibtex]
    @InProceedings{Verbeek16,
    Title = {Merging Alignments for Decomposed Replay},
    Author = {Verbeek, H. M. W and Aalst, W. M. P. v. d.},
    Booktitle = {Application and Theory of {P}etri Nets and Concurrency},
    Year = {2016},
    Address = {Torun, Poland},
    Editor = {Kordon, F and Moldt, D.},
    Month = {June},
    Pages = {219--239},
    Publisher = {Springer International Publishing},
    Series = {LNCS},
    Volume = {9698},
    Abstract = {In the area of process mining, conformance checking aims to find an optimal alignment between an event log (which captures the activities that actually have happened) and a Petri net (which describes expected or normative behavior). Optimal alignments highlight discrepancies between observed and modeled behavior. To find an optimal alignment, a potentially challenging optimization problem needs to be solved based on a predefined cost function for misalignments. Unfortunately, this may be very time consuming for larger logs and models and often intractable. A solution is to decompose the problem of finding an optimal alignment in many smaller problems that are easier to solve. Decomposition can be used to detect conformance problems in less time and provides a lower bound for the costs of an optimal alignment. Although the existing approach is able to decide whether a trace fits or not, it does not provide an overall alignment. In this paper, we provide an algorithm that is able provide such an optimal alignment from the decomposed alignments if this is possible. Otherwise, the algorithm produces a so-called pseudo-alignment that can still be used to pinpoint non-conforming parts of log and model. The approach has been implemented in ProM and tested on various real-life event logs.},
    Doi = {10.1007/978-3-319-39086-4_14},
    Url = {http://www.win.tue.nl/~hverbeek/wp-content/papercite-data/pdf/verbeek16.pdf}
    }

it is possible to merge subalignments back together into an alignment. However, this may not be possible for all subalignments, as some of them will contain conflicts on the borders of the subalignments. After merging, these subalignments are not an alignment, but a pseudo alignment.

After having done a decomposed replay that results in pseudo alignments, the “Replay with Recomposition” plug-in will do another decomposed replay, in which one of the conflicts is solved by combining the related subnets. As such, it resolves the conflict by recomposing these subnets into a single subnet.

Provided sufficient time (and resources), the “Replay with Recomposition” plug-in will return the same fitness value as the non-decomposed replay would, but possibly in less time. Furthermore, the “Replay with Recomposition” has the possibility to terminate earlier, based on some termination criteria. For example, this plug-in allows you to specify that you want to have the best possible fitness value, but that it may only take 10 minutes to compute it. This best possible fitness value will be an interval of a lower bound and an upper bound, with the guarantee that the exact fitness will be in that interval.

Configuration options

  1. Classifier and costsrecomposedreplayer1
    The first dialog allows you to configure which classifier should be used, and the move-on-log and the move-on-model costs. Note that the current plug-in does not allow you to specify different costs move-on-log costs etc.
  2. Transition-activity maprecomposedreplayer2The second dialog allows you to configure which transition labels are mapped onto which activities. Initially, a transition label is mapped onto an activity with the same name, if it exists, and to no activity ([invisible]) if it does not exist.
  3. Rejection of pseudo alignments
    recomposedreplayer3The third dialog allows you to configure which pseudo alignments should be rejected for another replay. A rejected pseudo alignment will not be replayed again. As a result of rejecting pseudo alignments, the returned fitness interval may grow. You can configure a threshold for the number of conflicts and a threshold for the time spent on the pseudo alignment.
  4. Termination of the recomposed replay
    recomposedreplayer4The fourth and last dialog allows you to configure when the recomposed replayer should terminate. Of course, the replay also terminates if no pseudo alignments remain, in which case the fitness interval only contains the actual fitness value. You can configure a threshold for the total amount of time (if this is set to 10 minutes, the replayer will not start another replay if 10 minutes have passed), a threshold for the percentage of alignments (if this is set to 90, the replayer will not start another replay if alignments have been constructed for at least 90% of the traces), a relative and absolute width for the fitness interval, and a threshold for the number of replays.

 

One Comment

  1. Eric

    The first configuration dialog now includes two new checkboxes:

    • a checkbox that can be used to estimate the model move costs for the empty trace, and
    • a checkbox to select whether or not to use the hide-and-reduce abstraction.

    To compute fitness, the replayer uses the fact that no alignment can have costs that exceed doing only model moves and log moves. To compute the cheapest costs of doing on model moves, it replays the empty trace on the model. However, this may take a while. By checking this box, the replayer will estimate these costs by taking the cheapest model move costs for any trace in the log.

    The replayer can be told to use the hide-and-reduce abstraction instead of the original abstraction (for obtaining subnets form the overall net). Chances of a border agreement are (slightly) better using the hide-and-reduce abstraction.

    In the third configuration dialog, the calculation time threshold is now set in seconds (instead of in milliseconds).

    A fifth configuration dialog has been added that allows the user to select on which activities the model may be split into parts. By default, all activities are selected. The decomposition obtained is the most fine-grained valid decomposition that splits only on the selected activities.

Leave a Reply