The management of business processes has recently received much attention, since it can support signi cant e ciency improvements in organizations. One of the most interesting problems is the description of a process model in a language, also equipped with an operational support, that allows checking the compliance of a process execution (trace) to the model. Another problem of interest is the induction of these models from data. In this paper, we present a logic-based approach for the induction of process models that are expressed by means of a probabilistic logic. The approach rst uses the DPML algorithm to extract a set of integrity constraints from a collection of traces. Then, the learned constraints are translated into Markov Logic formulas and the weights for each formula are tuned using the Alchemy system. The resulting theory allows to perform probabilistic classi cation of traces. We tested the proposed approach on a real database of university students' careers. The experiments show that the combination of DPML and Alchemy achieves better results than DPML alone.
Organizations usually rely on a number of processes to achieve their mission.
These processes are typically complex and involve a large number of people. The
performance of the organization critically depends on the quality and accuracy of
its processes. Formal ways of representing business processes have been studied
in the area of Business Processes Management (see e.g. [
Recently, the problem of automatically mining a structured description of a
business process directly from real data has been studied by many authors (see
e.g. [
Most work in the eld of Process Mining has been devoted to inducing models
in the form of graphs or Petri nets [
DecSerFlow [
Starting from them, in this paper we investigate the adoption of a logic-based
language for representing a process model that is able to encode probabilistic
information. In fact, the complexity and uncertainty of real world domains
require both the use of rst-order logic and the use of probability. Recently, various
languages have been proposed in the eld of Statistical Relational Learning that
combine the two. One of these is Markov Logic [
We propose to represent process models by means of Markov Logic. Moreover,
we present a logic-based approach for inducing these descriptions that involves
rst learning a logical theory with DPML [
The e ectiveness of the approach is illustrated by considering as processes the careers of real students at the University of Ferrara. The experiment showed that the combined use of DPML and Alchemy for Process Mining outperforms the use of DPML only.
The paper is organized as follows: we rst discuss how we represent execution traces and process models with logic programming. Then we present the learning technique we have adopted for performing Process Mining. After having evaluated the proposed approach on a real world dataset, we discuss related works and conclude. 2
A trace t is a sequence of events. Each event is described by a number of attributes. The only requirement is that one of the attributes describes the event type. Other attributes may be the executor of the event or event speci c information.
An example of a trace is ha; b; ci where a, b and c are events.
We de ne a process model P M as a formula in a language for which an interpreter exists that, when applied to a model P M and a trace t, returns answer yes if the trace is compliant with the description and false otherwise.
A bag of process traces L is called a log. The aim of Process Mining is to
infer a process model from a log. Usually, in Process Mining, only compliant
traces are used as input to the learning algorithm, see e.g. [
Representing Process Traces and Models with Logic A process trace can be represented as a logical interpretation (set of ground atoms): each event is modeled with an atom whose predicate is the event type and whose arguments store the attributes of the event. Moreover, the atom contains an extra argument indicating the position in the sequence. For example, the trace:
ha; b; ci can be represented with the interpretation fa(1); b(2); c(3)g.
Besides the trace, we may have some general knowledge that is valid for all the traces. This information will be called background knowledge and we assume that it can be represented as a normal logic program B. By using a background knowledge we are able to encode each trace parsimoniously, by storing only once the rules that are not speci c to a single trace but are true for every trace. For example, the background knowledge may contain clauses which de ne precedence and succession relations involving the argument 'position' of the atom representing an event.
Rather than simply t, we therefore consider M (B [ t), the model of the
program B [ t according to Clark's completion [
The process language we consider is a subset of the SCIFF language,
originally de ned in [
A process model in our language is a set of Integrity Constraints (ICs). An IC, C, is a logical formula of the form
order(bob; camera; T ); T < 10 !9T 1(ship(alice; camera; T 1)); bill(alice; bob; 100; T 1); T < T 1 _ 8T 1; V :bill(alice; bob; V; T 1); T < T 1 where Body, ConjPi i = 1; : : : ; n and ConjNj j = 1; : : : ; m are conjunctions of literals built over event atoms or over predicates de ned in the background knowledge.
We will use Body(C) to indicate Body and Head(C) to indicate the formula 9(ConjP1) _ : : : _ 9(ConjPn) _ 8:(ConjN1) _ : : : _ 8:(ConjNm) and call them respectively the body and the head of C. We will use HeadSet(C) to indicate the set fConjP1; : : : ; ConjPn; ConjN1; : : : ; ConjNmg. The quanti ers in the head apply to all the variables not appearing in the body. The variables of the body are implicitly universally quanti ed with scope the entire formula.
Body(C), ConjPi i = 1; : : : ; n and ConjNj j = 1; : : : ; m will be sometimes interpreted as sets of literals, the intended meaning will be clear from the context. All the formulas ConjPj in Head(C) will be called P disjuncts ; all the formulas ConjNj in Head(C) will be called N disjuncts.
An example of an IC is (1) (2)
The meaning of the IC (2) is the following: if bob has ordered a camera at a time T < 10, then alice must ship it and bill bob 100$ at a time T 1 later than T or alice must not bill bob any expense at a time T 1 later than T .
An IC C is true in an interpretation M (B [ t), written M (B [ t) j= C, if, for every substitution for which Body(C) is true in M (B [ t), there exists a disjunct 9(ConjPi) or 8:(ConjNj ) in Head(C) that is true in M (B [ t). If M (B [ t) j= C we say that the trace t is compliant with C. A process model H is true in an interpretation M (B [ t) if every IC of H is true in it and we write M (B [ t) j= H. We also say that trace t is compliant with H.
Similarly to what has been observed in [
If the N disjuncts in the head share some variables, then the following query must be issued ? Body; not(ConjP1); : : : not(ConjPn); not(not(ConjN1)); : : : ; not(not(ConjNm)) that ensures that the N disjuncts are tested separately without instantiating the variables.
If the query nitely fails, the IC is true in the interpretation. If the query succeeds, the IC is false in the interpretation. Otherwise nothing can be said. 2.2
In this section, we brie y describe the Declarative Process Model Learner (DPML)
algorithm that was proposed in [
DPML nds an IC theory solving the learning problem by searching the space of ICs. The space is structured using a generality relation based on the following de nition of subsumption.
De nition 1 (Subsumption). An IC D subsumes an IC C, written D C, i it exists a substitution for the variables in the body of D or in the N disjuncts of D such that { Body(D) Body(C) and { 8ConjP (D) 2 HeadSet(D); 9ConjP (C) 2 HeadSet(C) : ConjP (C)
ConjP (D) and { 8ConjN (D) 2 HeadSet(D); 9ConjN (C) 2 HeadSet(C) : ConjN (D) ConjN (C) If D subsumes C, then D is more general than C. For example, let us consider the following clauses:
C = accept(X) _ ref usal(X) D = accept(X) _ ref usal(X) E = accept(X) invitation(X) invitation(X) true Then C is more general than D and E, while D and E are not comparable.
The aim of DPML is to discover a set of clauses built through a re nement operator, on the base of the generality relation. In order to de ne a re nement operator, we must rst de ne the language bias.
The language bias consists of a set of IC templates which de ne the literals that can be added to clauses. In particular, each template speci es: { a set of literals BS allowed in the body, { a set of disjuncts HS allowed in the head. For each disjunct, the template speci es: whether it is a P or an N disjunct, the set of literals allowed in the disjunct.
As a consequence the language bias prescribes which re nements can be realized, so that a nite number of those have to be considered, performing the search in the space of ICs from speci c to general. Given an IC D, the nite set of re nements (D) of D is a set of ICs that are more general than D. The set of re nements (D) of D is obtained by performing one of the following operations: { adding a literal from the IC template for D to the body; { adding a disjunct from the IC template for D to the head; { adding a literal to an N disjunct in the head; { removing a literal from a P disjunct in the head.
Given a language bias which prescribes that the body literals must be chosen among finvitation(X); test(X)g and that the head disjuncts must be chosen among faccept(X); ref usal(X)g, an example of re nement sequence is: f alse accept(X) accept(X) true true invitation(X) accept(X) _ ref usal(X) invitation(X)
The DPML algorithm solves the following learning problem: Given { a space of possible process models H { a set I+ of positive traces; { a set I of negative traces; { a de nite clause background theory B. function DPML(I+; I ; B) initialize H := ; do
C := FindBestIC(I+; I ; B) if C 6= ; then add C to H remove from I all interpretations
that are false for C while C 6= ; and I is not empty return H function FindBestIC(I+; I ; B) initialize Beam := ff alse trueg initialize BestIC := ; while Beam is not empty do initialize N ewBeam := ; for each IC C in Beam do for each re nement Ref of C do if Ref is better than
BestIC then BestIC := Ref if Ref is not to be pruned then add Ref to N ewBeam if size of N ewBeam > M axBS then remove worst clause
from N ewBeam
Beam := N ewBeam return BestIC Find: a process model H 2 H such that { for all i+ 2 I+, M (B [ i+) j= H; { for all i 2 I , M (B [ i ) 6j= H; If M (B [ i) j= C we say that IC C covers the trace i and if M (B [ i) 6j= C we say that C rules out the trace i.
Every IC in the learned theory is seen as a clause that must be true in all the positive traces (compliant traces) and false in some negative traces (non compliant traces). The theory composed of all the ICs must be such that all the ICs are true when considering a compliant trace and at least one IC is false when considering a non compliant one.
The DPML algorithm is an adaptation of ICL [
The IC to be added in every iteration of the covering loop is returned by function FindBestIC. It looks for an IC by using beam search with p( jC) as a heuristic function. The search starts from the IC f alse true that is the most speci c and rules out all the negative traces but also all the positive traces. ICs in the beam are gradually generalized by using the re nement operator. M axBS is a user-de ned constant storing the maximum size of the beam.
At the end of the re nement cycle, the best IC found so far is returned. 2.3
Markov Logic (ML) [
De nition 2 (Markov logic network). A Markov logic network (MLN) L is a set of pairs (Fi; wi), where Fi is a formula in rst-order logic and wi is a real number. Together with a nite set of constants C = fc1; c2; : : : ; cmg, it de nes a Markov network ML;C as follows: 1. ML;C contains one binary node for each possible grounding of each atom appearing in L. The value of the node is 1 if the ground atom is true, and 0 otherwise. 2. ML;C contains one feature (real-valued function) for each possible grounding of each formula Fi in L. The value of this feature is 1 if the ground formula is true, and 0 otherwise. The weight of the feature associated to Fi is wi.
For example, an MLN containing the formula 8xSmokes(x) ! Cancer(x) (smoking causes cancer) applied to the set of constants C = fAnna; Bobg yields the features Smokes(Anna) !Cancer(Anna) and Smokes(Bob) !Cancer(Bob), and a ground Markov network with 4 nodes (Smokes(Anna), Cancer(Anna), Smokes(Bob), Cancer(Bob)).
A possible world x is an assignment of truth values to every ground atom. The probability distribution speci ed by the ground Markov network ML;C over possible worlds x is given by
P (x) =
exp impossible. The basic idea in Markov Logic is to soften these constraints: when a world violates one of them it is just less probable, but not impossible. The weight associated to each formula re ects how strong the constraint is: the higher the weight, the greater the di erence in probability between a world that satis es the formula and one that does not, other things being equal.
Once an IC theory has been learned from data, integrity constraints are
transformed into ML formulas and weights are learned for them using the
discriminative weight learning algorithm of [
Each IC of the form (1) is translated into the following ML formula: Body ^ :(ConjP1) ^ : : : ^ :(ConjPn) ^(ConjN1) ^ : : : ^ (ConjNm) ! neg (4) where neg means that the trace is negative. In absence of disjuncts in the head, the IC Body ! f alse reduces to Body ! neg. The head of all the formulas always contains only the atom neg, while all disjuncts in the head are moved to the body.
An example of IC referred to the analyzed domain is: true _ 8F; G; I:enrollment2(F; G; OC; I))): !8A; B; C; D; E; I:registration(A; B; C; D; E; 2005; I) This IC states that the students (with ID I) who graduated (positive traces) do not present registration in the year 2005 or an enrollment in the second year as an out-of-course (OC) student.
The translation into a formula in Markov logic is: registration(A; B; C; D; E; 2005)^ enrollment2(F; G; oc) ! neg The resulting MLN can then be used to infer the probability of neg given a database consisting of atoms representing the trace. 3
Research in machine learning has shifted away from simply presenting accuracy results when performing an empirical validation of new algorithms. This is especially true when evaluating algorithms that output probabilities of class values. Provost et al. (1998) have argued that simply using accuracy results can be misleading. They recommended to use Receiver Operator Characteristic (ROC) curves when evaluating binary decision problems. ROC curves show how the 1 http://alchemy.cs.washington.edu/ number of correctly classi ed positive examples varies with the number of incorrectly classi ed negative examples. In a binary decision problem, a classi er labels examples as either positive or negative. The decision made by the classi er can be represented in a structure known as a confusion matrix, that has four categories: True positives (TP) are examples correctly labeled as positives; False positives (FP) refer to negative examples incorrectly labeled as positive; True negatives (TN) correspond to negatives correctly labeled as negative; nally, false negatives (FN) refer to positive examples incorrectly labeled as negative. The confusion matrix can be used to construct a point in ROC space: one plots the False Positive Rate (FPR) on the x-axis and the True Positive Rate (TPR) on the y-axis. The FPR measures the fraction of negative examples that are misclassi ed as positive (FPR=FP/(FP+TN)). The TPR measures the fraction of positive examples that are correctly labeled (TPR=TP/(TP+FN)). Informally, one point in ROC space is better than another if it is to the northwest (TPR is higher, FPR is lower, or both) of the rst. The point (0; 1) represents perfect classi cation.
A discrete classi er, which gives only a class decision, i.e., a Yes or No on each instance, produces a single point in ROC space. Some classi ers instead yield an instance probability or score, a numeric value that represents the degree to which an instance is a member of the positive class. An important point about ROC graphs is that they measure the ability of a classi er to produce good relative instance scores. A classi er needs not produce accurate, calibrated probability estimates; it needs only produce relative accurate scores that serve to discriminate positive and negative instances.
Starting from the set of test examples, the probabilistic classi er's estimate that each example is positive, the number of positive and negative examples, an e cient generation algorithm of ROC curves has been proposed which rst sorts the list of examples in ascending probability order and then, starting from the beginning of the list, for each positive instance increments TP and for every negative instance increments FP. It maintains a stack R of ROC points, pushing a new point onto R after each instance is processed. Finally it graphs the set R which contains the points on the curve (and not a single point like a discrete classi er).
ROC curves are typically generated to evaluate the performance of a machine learning algorithm on a given dataset. To evaluate and also to compare di erent classi ers one must reduce ROC curve to a single scalar value representing expected performance. A common method is to calculate the area under the ROC curve, abbreviated AUC: it may be computed easily using a small modi cation of the previous algorithm. Since the AUC is a portion of the area of the unit square, its value will always be between 0 and 1. Given 2 classi ers and their AUC, the one with the greater area has better average performance.
Our goal is to demonstrate that the combined use of DPML, for learning an IC theory, and Alchemy, for learning weights for formulas, produces better results than the sharp classi cation realized by the IC theory alone.
The experiments have been performed over a real dataset regarding university students, where the careers of students that graduated are positive traces and the careers of students who did not nish their studies are negative ones. We want to predict whether a student graduates on the basis of her career. To perform our experiments, we collected 813 careers of students enrolled at the Faculty of Engineering of the University of Ferrara from 2004 to 2009. The traces have been labeled as compliant or non compliant with respect to the classi cation speci ed above. There are 327 positive and 486 negative traces.
We rst induce an IC theory from these data. Every trace was therefore adapted to the format required by the DPML algorithm, transforming it into an interpretation. We considered the main activities performed by a student together with parameters describing the activities. An example of an interpretation for a student is the following: fregistration(par1; : : : ; parn; 1); exam(par1; : : : ; parm; 2); exam(par1; : : : ; parm; 3); : : : career end(par1; n)g where pari means the i-th parameter for a certain activity. Each activity has a xed number of parameters which re ect the corresponding attributes stored in the database used. The complete list of logical predicates used, corresponding to activities, is the following: { registration, which stores some personal and school information about a student, with parameters type, mark and year of high school diploma, town and country of residence, year of registration at university, student's ID; { enrollmentN , with N=1..9, which stores the enrollments to years following the rst (of registration), with parameters enrollment year, course year (1,2,3), student's status (out-of-course or not), student's ID; { exam, with parameters course id, mark (number), honours (yes/no) and mark category (low, medium, high); { career end which stores the career conclusion, with values degree (positive traces) or abandon, not-renewed enrollment, transfer to another faculty, transfer to another University (negative traces). A ten-fold cross-validation was used, i.e., the dataset was divided into ten sets (containing roughly the same proportion of positive and negative traces as the whole dataset) and ten experiments were performed, where nine sets were used for training and the remaining one for testing, i.e., for evaluating the accuracy of the learned theory. In particular, test sets contain either 33 positive and 49 negative traces or 32 positive and 48 negative traces.
The same language bias was used in all ten experiments, including two IC templates. The rst template prescribed as body literal the exam predicate (using one atom for every value of honours parameter) and as head disjunct the registration predicate and the enrollment1 predicate; the second template prescribed as body literals the registration predicate (one atom for every value of year parameter) and the enrollmentN predicate with N=1..9 (one atom for every value of enrollment year, of course year, of student0s status, and for every value of the couple course year+student's status), and as head disjunct the registration predicate (one atom for every value of town and of country of residence).
The accuracy is de ned as the number of compliant traces that are correctly classi ed as compliant by the learned model plus the number of non compliant traces that are correctly classi ed as not compliant divided by the total number of traces.
Ten di erent IC theories were learned, composed of a number of rules between 25 and 31. The accuracy of the theories on the test sets ranges from 54% to 86%, with an average of 67.5%. Examples of ICs that were obtained, in SCIFF language, are: 8A; B; C; D; E; I registration(A; rimini; B; C; D; E; I ) ! f alse: which states that students from the town of Rimini didn't graduate, true ! 8A; B; I:enrollment6(2009; A; B; I): which states that students who enrolled 6 times (year 2009 being the sixth after registration) didn't graduate, 8A; B; C; D; E; I registration(A; bologna; B; C; D; E; I ) ! 8F; G; I:enrollment1(2005; F; G; I): which states that students living in Bologna and enrolled the rst time in 2005 didn't graduate.
The second step was the assignment of weights to the ICs, by creating ten MLN containing the theories translated into ML. Each of the ten MLNs were given as input to Alchemy for discriminative weight learning.
Ten MLNs were also generated from the learned IC theories by assigning the pseudo-in nite weight 1010 to all the clauses, in order to approximate a purely logical theory.
The corresponding MLNs to the three ICs above are respectively: registration(A; rimini; B; C; D; E) ! neg enrollment6(2009; A; B) ! neg registration(A; bologna; B; C; D; E) ^ enrollment1(2005; A; B) ! neg
In the third step, we computed the probability of each test trace of being
negative. This was performed by running the belief propagation inference
algorithm of [
Finally, we compared the sharp MLN with the weighted MLN using the the
average area under the ROC curve (AUC) [
Most works on process mining deal with process models in the form of graphs
or Petri nets, that represent the allowed sequences of events as paths in the
diagram. [
[
In [
Recently, a new approach for the representation of process models has appeared, in which the models are seen as sets of constraints over the executions of the process. These models are called declarative because they state the conditions that process executions must satisfy rather than encoding them as paths in graphs.
Examples of declarative languages for representing process models are
DecSerFlow [
[
This paper extends the works [
Recently, [
We propose a methodology, based both on Logic and Statistical Relational Learning, for analyzing a log containing several traces of a process, labeled as compliant or non-compliant. From them we learn a set of declarative constraints expressed as ICs. Then we represent ICs in Markov Logic, a language extending rst-order logic, to obtain a probabilistic classi cation of traces, by using the Alchemy system. Finally we evaluate the performances of the two models concluding that probabilistic ICs are more accurate than the pure logical ones. The experiments have been performed on process traces belonging to a real dataset of university students' careers.
Supplementary material, including the code of the systems and an example dataset, can be found at http://sites.google.com/a/unife.it/ml/pdpm/
This work was possible thanks to the Audit O ce of the University of Ferrara, in particular Alberto Domenicali and Susanna Nanetti, that supplied the university dataset for experiments.