{"id":109,"date":"2020-02-07T12:07:41","date_gmt":"2020-02-07T11:07:41","guid":{"rendered":"https:\/\/blog.rwth-aachen.de\/pads\/?p=109"},"modified":"2020-02-07T12:57:27","modified_gmt":"2020-02-07T11:57:27","slug":"beyond-precision-and-recall-using-earth-movers-distance-stochastics","status":"publish","type":"post","link":"https:\/\/blog.rwth-aachen.de\/pads\/2020\/02\/07\/beyond-precision-and-recall-using-earth-movers-distance-stochastics\/","title":{"rendered":"Beyond Precision and Recall: Using Earth Mover\u2019s Distance & Stochastics"},"content":{"rendered":"\n

This post is by Prof. Dr. Wil van der Aalst<\/a>, Chairholder in the Process And Data Science group at RWTH Aachen University. Contact him via email for further inquiries.<\/em><\/p>\n\n\n\n

Conformance checking aims to uncover differences between a process model and an event log. Initially, process mining focused on discovering process models from event data, but in recent years, the use and importance of conformance checking increased. Many conformance checking techniques and measures have been proposed. Typically, these take into account the frequencies of traces in the event log, but do not consider the probabilities of these traces in the model. This asymmetry leads to various complications. A novel way to approach this, is to assume probabilities and subsequently use the Earth Movers’ Distance<\/em> (EMD) between stochastic languages representing models and event logs.<\/p>\n\n\n\n

The Earth Movers’ Distance<\/em> (EMD) provides and simple and intuitive conformance notion. The typical problems related to precision vanish immediately! Moreover, the approach is extensible to other perspectives (including time and resources) and can also be applied to concept drift detection and comparative process mining. This blog post summarizes part of my presentation given on 19-11-2019 in the weekly PADS Seminar Series (slides are attached at the bottom of the page).<\/p>\n\n\n\n

\nWhat is the problem?<\/h2>\n\n\n\n

To explain the problem, let us consider the following process model and five event logs (L1<\/sub> \u2013 L5<\/sub>).<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

<\/p>\n\n\n\n
L1<\/sub> <\/td>= [\u3008a,b,d,e\u3009490<\/sup>,\u3008a,d,b,e\u3009490<\/sup>,\u3008a,c,d,e\u300910<\/sup>,\u3008a,d,c,e\u300910<\/sup>]<\/td><\/tr>
L2<\/sub><\/td>= [\u3008a,b,d,e\u3009245<\/sup>,\u3008a,d,b,e\u3009245<\/sup>,\u3008a,c,d,e\u30095<\/sup>,\u3008a,d,c,e\u30095<\/sup>,\u3008a,b,e\u3009500<\/sup>]<\/td><\/tr>
L3<\/sub><\/td>= [\u3008a,b,d,e\u3009489<\/sup>,\u3008a,d,b,e\u3009489<\/sup>,\u3008a,c,d,e\u300910<\/sup>,\u3008a,d,c,e\u300910<\/sup>,\u3008a,b,e\u30092<\/sup>]<\/td><\/tr>
L4<\/sub><\/td>= [\u3008a,b,d,e\u3009500<\/sup>,\u3008a,d,b,e\u3009500<\/sup>]<\/td><\/tr>
L5<\/sub><\/td>= [\u3008a,c,d,e\u3009500<\/sup>,\u3008a,d,c,e\u3009500<\/sup>]<\/td><\/tr><\/tbody><\/table>\n\n\n\n

Each trace in L1<\/sub> matches a trace of the model and vice versa. Hence, all existing recall and precision measures tend to give a high score (i.e., good conformance). Half of the traces in L2<\/sub> do not fit the model (\u3008a,b,e\u3009is impossible according to the model, but occurs 500 times). Hence, all existing recall measures will report a low recall score for L2<\/sub>. However, these measures will report a high score for recall when L3<\/sub> is considered. The reason is that in L3<\/sub>, 99.8% of the traces are fitting (\u3008a,b,e\u3009occurs only twice). Existing recall measures tend to give high scores when L4<\/sub> and L5<\/sub> are considered since the model can reproduce all traces observed. However, both L4<\/sub> and L5<\/sub> are only covering two of the four traces allowed by the process model. Hence, existing precision measures tend to give a lower score for L4<\/sub> and L5<\/sub>. Moreover, due to symmetry, there is no reason to consider L4<\/sub> and L5<\/sub> to be different from a precision point of view.<\/p>\n\n\n\n

The above\nanalysis of existing recall measures shows that frequencies\nmatter<\/em>. L2<\/sub> and L3<\/sub> have the same\nsets of traces, but 50% of the traces of L2<\/sub> are\nfitting and 99.8% of the traces of L3<\/sub> are fitting.\nHence, most recall measures will consider L3<\/sub> to\nconform much better than L2<\/sub>. The logical counterpart of\nfrequencies in event logs are routing probabilities in process\nmodels. However, almost all existing measures ignore such routing\nprobabilities. This leads to an asymmetry. <\/p>\n\n\n\n

Therefore, we\nargue that also probabilities matter<\/em>.<\/p>\n\n\n\n

Probabilities matter!<\/h2>\n\n\n\n

We start by adding\nprobabilities to the process model introduced before.<\/p>\n\n\n\n

The numbers attached to transitions can be interpreted as weights. The probability of trace\u3008a,d,b,e\u3009is 0.5\u00d70.98 = 0.49, the probability of trace\u3008a,d,c,e\u3009is 0.5 \u00d70.02 = 0.01, etc. Hence, the model describes a so-called stochastic language: <\/p>\n\n\n\n
M <\/td>= [\u3008a,b,d,e\u30090.49<\/sup>,\u3008a,d,b,e\u30090.49<\/sup>,\u3008a,c,d,e\u30090.01<\/sup>,\u3008a,d,c,e\u30090.01<\/sup>]<\/td><\/tr><\/tbody><\/table>\n\n\n\n

Similarly, we can convert trace frequencies into probabilities: <\/p>\n\n\n\n
L1<\/sub> <\/td>= [\u3008a,b,d,e\u30090.49<\/sup>,\u3008a,d,b,e\u30090.49<\/sup>,\u3008a,c,d,e\u30090.01<\/sup>,\u3008a,d,c,e\u30090.01<\/sup>]<\/td><\/tr>
L2<\/sub><\/td>= [\u3008a,b,d,e\u30090.245<\/sup>,\u3008a,d,b,e\u30090.245<\/sup>,\u3008a,c,d,e\u30090.005<\/sup>,\u3008a,d,c,e\u30090.005<\/sup>,\u3008a,b,e\u30090.5<\/sup>]<\/td><\/tr>
L3<\/sub><\/td>= [\u3008a,b,d,e\u30090.489<\/sup>,\u3008a,d,b,e\u30090.489<\/sup>,\u3008a,c,d,e\u30090.01<\/sup>,\u3008a,d,c,e\u30090.01<\/sup>,\u3008a,b,e\u30090.002<\/sup>]<\/td><\/tr>
L4<\/sub><\/td>= [\u3008a,b,d,e\u30090.5<\/sup>,\u3008a,d,b,e\u30090.5<\/sup>]<\/td><\/tr>
L5<\/sub><\/td>= [\u3008a,c,d,e\u30090.5<\/sup>,\u3008a,d,c,e\u30090.5<\/sup>]<\/td><\/tr><\/tbody><\/table>\n\n\n\n

By converting event\nlogs and process models to stochastic languages, conformance is\nreduced to the problem of comparing stochastic languages.<\/p>\n\n\n\n

Consider model M and\nthe five event logs L1<\/sub>, L2<\/sub>, L3<\/sub>, L4<\/sub>,\nand L5<\/sub>. Obviously, L3<\/sub> is closer to M\nthan L2<\/sub>. Similarly, L4<\/sub> is closer to M than\nL5<\/sub>. We propose to use the so-called Earth Mover’s\nDistance<\/em> (EMD) to compare stochastic languages. If the\nprobabilities of traces are considered as piles of sand, then EMD is\nthe minimum cost of moving the sand from one distribution to another.\nEMD requires a distance notion. For our Earth Movers’ Stochastic\nConformance notion, we provided several distance notions, e.g., the\nnormalized edit distance between two traces.<\/p>\n\n\n\n

Earth Movers’ Stochastic Conformance<\/h2>\n\n\n\n

If we assume the\nnormalized edit distance between traces, then the EMD distance is a\nnumber between 0 (identical, i.e., fully conforming) and 1 (worst\npossible conformance). For our model M and logs L1<\/sub>,L2<\/sub>,\n\u2026, L5<\/sub> we find the following distances: 0 for L1<\/sub>,\n0.125 for L2<\/sub>, 0.0005 for L3<\/sub>, 0.005 for L4<\/sub>,\nand 0.245 for L5<\/sub>. Note that distance is the inverse of\nsimilarity, i.e., for model M and logs L1<\/sub>,L2<\/sub>,\n\u2026, L5<\/sub> we find the following Earth Movers’\nStochastic Conformance similarity measures: 1 for L1<\/sub>,\n0.875 for L2<\/sub>, 0.9995 for L3<\/sub>, 0.995 for L4<\/sub>,\nand 0.755 for L5<\/sub>. Hence, given M, L1<\/sub> has\nthe best conformance, L3<\/sub> is much better than L2<\/sub>,\nand L4<\/sub> is much better than L5<\/sub>. This\nmatches our intuition, e.g., L5<\/sub> does not have any\nexecutions of b although, according to the model, b should be\nexecuted for 98% of cases. Note that there is just one conformance\nmeasure and not two separate measures for recall and precision. This\nmakes sense considering that increasing the probability of one trace\nshould coincide with lowering the probabilities of other traces.<\/p>\n\n\n\n

Just the starting point!<\/h2>\n\n\n\n

\nThe approach is very promising and has been implemented in ProM. This\nwas mostly done by Sander Leemans from QUT. Next, to these\nconformance measures, we also defined various types of diagnostics to\nidentify conformance problems in both log and model. In addition,\nchallenges related to infinite loops, duplicate activities, and\nsilent activities have been addressed. Recently, also Tobias\nBrockhoff joined the team and is focusing on using the EMD notion to\nconcept drift, i.e., detecting when and how process change. Moreover,\nhe also extended the above techniques with time. This allows us to\nsee how performance is changing. These techniques are being applied\nin the Internet of Production (IoP) Cluster of Excellence at RWTH.\nThe work of Tobias can be used to find and diagnose performance\nproblems and uncover changes in routing and delays in production\nsystems.<\/p>\n\n\n\n

Learn More?<\/h2>\n\n\n\n

Check out the slides of the PADS Seminar Series<\/a>.<\/p>\n\n\n\n

  1. S.J.J. Leemans, A.F. Syring, and W.M.P. van der Aalst. Earth Movers’ Stochastic Conformance Checking<\/strong>. In T.T. Hildebrandt, B.F. van Dongen, M. R\u00f6glinger, and J. Mendling, editors, Business Process Management Forum (BPM Forum 2019), volume 360 of Lecture Notes in Business Information Processing<\/em>, pages 127-143. Springer-Verlag, Berlin, 2019. <\/li>
  2. W.M.P. van der Aalst, A. Adriansyah, and B. van Dongen. Replaying History on Process Models for Conformance Checking and Performance Analysis<\/strong>. WIREs Data Mining and Knowledge Discovery<\/em>, 2(2):182-192, 2012. <\/li><\/ol>\n","protected":false},"excerpt":{"rendered":"

    This post is by Prof. Dr. Wil van der Aalst, Chairholder in the Process And Data Science group at RWTH Aachen University. Contact him via email for further inquiries. Conformance […]<\/p>\n","protected":false},"author":1679,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"c2c_always_allow_admin_comments":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-109","post","type-post","status-publish","format-standard","hentry","category-allgemein"],"_links":{"self":[{"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/posts\/109","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/users\/1679"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/comments?post=109"}],"version-history":[{"count":16,"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/posts\/109\/revisions"}],"predecessor-version":[{"id":130,"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/posts\/109\/revisions\/130"}],"wp:attachment":[{"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/media?parent=109"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/categories?post=109"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/tags?post=109"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}