30 results on '"Taymouri, Farbod"'
Search Results
2. A Deep Adversarial Model for Suffix and Remaining Time Prediction of Event Sequences
- Author
-
Taymouri, Farbod, La Rosa, Marcello, and Erfani, Sarah M.
- Subjects
Computer Science - Machine Learning ,Computer Science - Artificial Intelligence - Abstract
Event suffix and remaining time prediction are sequence to sequence learning tasks. They have wide applications in different areas such as economics, digital health, business process management and IT infrastructure monitoring. Timestamped event sequences contain ordered events which carry at least two attributes: the event's label and its timestamp. Suffix and remaining time prediction are about obtaining the most likely continuation of event labels and the remaining time until the sequence finishes, respectively. Recent deep learning-based works for such predictions are prone to potentially large prediction errors because of closed-loop training (i.e., the next event is conditioned on the ground truth of previous events) and open-loop inference (i.e., the next event is conditioned on previously predicted events). In this work, we propose an encoder-decoder architecture for open-loop training to advance the suffix and remaining time prediction of event sequences. To capture the joint temporal dynamics of events, we harness the power of adversarial learning techniques to boost prediction performance. We consider four real-life datasets and three baselines in our experiments. The results show improvements up to four times compared to the state of the art in suffix and remaining time prediction of event sequences, specifically in the realm of business process executions. We also show that the obtained improvements of adversarial training are superior compared to standard training under the same experimental setup.
- Published
- 2021
3. Encoder-Decoder Generative Adversarial Nets for Suffix Generation and Remaining Time Prediction of Business Process Models
- Author
-
Taymouri, Farbod and La Rosa, Marcello
- Subjects
Computer Science - Machine Learning ,Statistics - Machine Learning - Abstract
This paper proposes an encoder-decoder architecture grounded on Generative Adversarial Networks (GANs), that generates a sequence of activities and their timestamps in an end-to-end way. GANs work well with differentiable data such as images. However, a suffix is a sequence of categorical items. To this end, we use the Gumbel-Softmax distribution to get a differentiable continuous approximation. The training works by putting one neural network against the other in a two-player game (hence the "adversarial" nature), which leads to generating suffixes close to the ground truth. From the experimental evaluation it emerges that the approach is superior to the baselines in terms of the accuracy of the predicted suffixes and corresponding remaining times, despite using a naive feature encoding and only engineering features based on control flow and events completion time., Comment: arXiv admin note: substantial text overlap with arXiv:2003.11268
- Published
- 2020
4. Predictive Business Process Monitoring via Generative Adversarial Nets: The Case of Next Event Prediction
- Author
-
Taymouri, Farbod, La Rosa, Marcello, Erfani, Sarah, Bozorgi, Zahra Dasht, and Verenich, Ilya
- Subjects
Computer Science - Machine Learning ,Statistics - Machine Learning - Abstract
Predictive process monitoring aims to predict future characteristics of an ongoing process case, such as case outcome or remaining timestamp. Recently, several predictive process monitoring methods based on deep learning such as Long Short-Term Memory or Convolutional Neural Network have been proposed to address the problem of next event prediction. However, due to insufficient training data or sub-optimal network configuration and architecture, these approaches do not generalize well the problem at hand. This paper proposes a novel adversarial training framework to address this shortcoming, based on an adaptation of Generative Adversarial Networks (GANs) to the realm of sequential temporal data. The training works by putting one neural network against the other in a two-player game (hence the adversarial nature) which leads to predictions that are indistinguishable from the ground truth. We formally show that the worst-case accuracy of the proposed approach is at least equal to the accuracy achieved in non-adversarial settings. From the experimental evaluation it emerges that the approach systematically outperforms all baselines both in terms of accuracy and earliness of the prediction, despite using a simple network architecture and a naive feature encoding. Moreover, the approach is more robust, as its accuracy is not affected by fluctuations over the case length.
- Published
- 2020
5. Business Process Variant Analysis based on Mutual Fingerprints of Event Logs
- Author
-
Taymouri, Farbod, La Rosa, Marcello, and Carmona, Josep
- Subjects
Computer Science - Machine Learning ,Statistics - Machine Learning - Abstract
Comparing business process variants using event logs is a common use case in process mining. Existing techniques for process variant analysis detect statistically-significant differences between variants at the level of individual entities (such as process activities) and their relationships (e.g. directly-follows relations between activities). This may lead to a proliferation of differences due to the low level of granularity in which such differences are captured. This paper presents a novel approach to detect statistically-significant differences between variants at the level of entire process traces (i.e. sequences of directly-follows relations). The cornerstone of this approach is a technique to learn a directly follows graph called mutual fingerprint from the event logs of the two variants. A mutual fingerprint is a lossless encoding of a set of traces and their duration using discrete wavelet transformation. This structure facilitates the understanding of statistical differences along the control-flow and performance dimensions. The approach has been evaluated using real-life event logs against two baselines. The results show that at a trace level, the baselines cannot always reveal the differences discovered by our approach, or can detect spurious differences.
- Published
- 2019
6. Business Process Variant Analysis: Survey and Classification
- Author
-
Taymouri, Farbod, La Rosa, Marcello, Dumas, Marlon, and Maggi, Fabrizio Maria
- Subjects
Computer Science - Other Computer Science - Abstract
Process variant analysis aims at identifying and addressing the differences existing in a set of process executions enacted by the same process model. A process model can be executed differently in different situations for various reasons, e.g., the process could run in different locations or seasons, which gives rise to different behaviors. Having intuitions about the discrepancies in process behaviors, though challenging, is beneficial for managers and process analysts since they can improve their process models efficiently, e.g., via interactive learning or adapting mechanisms. Several methods have been proposed to tackle the problem of uncovering discrepancies in process executions. However, because of the interdisciplinary nature of the challenge, the methods and sorts of analysis in the literature are very heterogeneous. This article not only presents a systematic literature review and taxonomy of methods for variant analysis of business processes but also provides a methodology including the required steps to apply this type of analysis for the identification of variants in business process executions.
- Published
- 2019
7. Discovering Unseen Behaviour from Event Logs
- Author
-
Armas Cervantes, Abel, Taymouri, Farbod, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bernardinello, Luca, editor, and Petrucci, Laure, editor
- Published
- 2022
- Full Text
- View/download PDF
8. Business Process Variant Analysis Based on Mutual Fingerprints of Event Logs
- Author
-
Taymouri, Farbod, La Rosa, Marcello, Carmona, Josep, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Dustdar, Schahram, editor, Yu, Eric, editor, Salinesi, Camille, editor, Rieu, Dominique, editor, and Pant, Vik, editor
- Published
- 2020
- Full Text
- View/download PDF
9. Discovering Unseen Behaviour from Event Logs
- Author
-
Armas Cervantes, Abel, primary and Taymouri, Farbod, additional
- Published
- 2022
- Full Text
- View/download PDF
10. Business process variant analysis: Survey and classification
- Author
-
Taymouri, Farbod, Rosa, Marcello La, Dumas, Marlon, and Maggi, Fabrizio Maria
- Published
- 2021
- Full Text
- View/download PDF
11. Model and Event Log Reductions to Boost the Computation of Alignments
- Author
-
Taymouri, Farbod, Carmona, Josep, van der Aalst, Wil M. P., Series Editor, Mylopoulos, John, Series Editor, Rosemann, Michael, Series Editor, Shaw, Michael J., Series Editor, Szyperski, Clemens, Series Editor, Ceravolo, Paolo, editor, Guetl, Christian, editor, and Rinderle-Ma, Stefanie, editor
- Published
- 2018
- Full Text
- View/download PDF
12. An Evolutionary Technique to Approximate Multiple Optimal Alignments
- Author
-
Taymouri, Farbod, Carmona, Josep, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Pandu Rangan, C., Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Weske, Mathias, editor, Montali, Marco, editor, Weber, Ingo, editor, and vom Brocke, Jan, editor
- Published
- 2018
- Full Text
- View/download PDF
13. A Deep Adversarial Model for Suffix and Remaining Time Prediction of Event Sequences
- Author
-
Taymouri, Farbod, primary, La Rosa, Marcello, additional, and Erfani, Sarah M., additional
- Published
- 2021
- Full Text
- View/download PDF
14. Business Process Variant Analysis Based on Mutual Fingerprints of Event Logs
- Author
-
Taymouri, Farbod, primary, La Rosa, Marcello, additional, and Carmona, Josep, additional
- Published
- 2020
- Full Text
- View/download PDF
15. Predictive Business Process Monitoring via Generative Adversarial Nets: The Case of Next Event Prediction
- Author
-
Taymouri, Farbod, primary, Rosa, Marcello La, additional, Erfani, Sarah, additional, Bozorgi, Zahra Dasht, additional, and Verenich, Ilya, additional
- Published
- 2020
- Full Text
- View/download PDF
16. Log- and Model-Based Techniques for Security-Sensitive Tackling of Obstructed Workflow Executions
- Author
-
Holderer, Julius, Carmona, Josep, Taymouri, Farbod, Müller, Günter, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Koutny, Maciej, editor, Kleijn, Jetty, editor, and Penczek, Wojciech, editor
- Published
- 2017
- Full Text
- View/download PDF
17. Aligning Modeled and Observed Behavior: A Compromise Between Computation Complexity and Quality
- Author
-
van Dongen, Boudewijn, Carmona, Josep, Chatain, Thomas, Taymouri, Farbod, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Dubois, Eric, editor, and Pohl, Klaus, editor
- Published
- 2017
- Full Text
- View/download PDF
18. A Recursive Paradigm for Aligning Observed Behavior of Large Structured Process Models
- Author
-
Taymouri, Farbod, Carmona, Josep, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, La Rosa, Marcello, editor, Loos, Peter, editor, and Pastor, Oscar, editor
- Published
- 2016
- Full Text
- View/download PDF
19. Aligning Modeled and Observed Behavior: A Compromise Between Computation Complexity and Quality
- Author
-
van Dongen, Boudewijn, primary, Carmona, Josep, additional, Chatain, Thomas, additional, and Taymouri, Farbod, additional
- Published
- 2017
- Full Text
- View/download PDF
20. Business process variant analysis based on mutual fingerprints of event logs
- Author
-
Universitat Politècnica de Catalunya. Doctorat en Computació, Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals, Taymouri, Farbod, La Rosa, Marcello, Carmona Vargas, Josep, Universitat Politècnica de Catalunya. Doctorat en Computació, Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals, Taymouri, Farbod, La Rosa, Marcello, and Carmona Vargas, Josep
- Abstract
Comparing business process variants using event logs is a common use case in process mining. Existing techniques for process variant analysis detect statistically-significant differences between variants at the level of individual entities (such as process activities) and their relationships (e.g. directly-follows relations between activities). This may lead to a proliferation of differences due to the low level of granularity in which such differences are captured. This paper presents a novel approach to detect statistically-significant differences between variants at the level of entire process traces (i.e. sequences of directly-follows relations). The cornerstone of this approach is a technique to learn a directly-follows graph called mutual fingerprint from the event logs of the two variants. A mutual fingerprint is a lossless encoding of a set of traces and their duration using discrete wavelet transformation. This structure facilitates the understanding of statistical differences along the control-flow and performance dimensions. The approach has been evaluated using real-life event logs against two baselines. The results show that at a trace level, the baselines cannot always reveal the differences discovered by our approach, or can detect spurious differences., This research is partly funded by the Australian Research Council (DP180102839) and Spanish funds MINECO and FEDER (TIN2017-86727-C2-1-R)., Peer Reviewed, Postprint (author's final draft)
- Published
- 2020
21. Computing alignments of well-formed process models using local search
- Author
-
Universitat Politècnica de Catalunya. Doctorat en Computació, Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals, Taymouri, Farbod, Carmona Vargas, Josep, Universitat Politècnica de Catalunya. Doctorat en Computació, Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals, Taymouri, Farbod, and Carmona Vargas, Josep
- Abstract
The alignment of observed and modeled behavior is an essential element for organizations, since it opens the door for conformance checking and enhancement of processes. The state-of-the-art technique for computing alignments has exponential time and space complexity, hindering its applicability for medium and large instances. In this article, a novel approach is presented to tackle the challenge of computing an alignment for large-problem instances that correspond to well-formed process models. Given an observed trace, first it uses a novel replay technique to find an initial candidate trace in the model. Then a local search framework is applied to try to improve the alignment until no further improvement is possible. The implementation of the presented technique reveals a magnificent reduction both in computation time and in memory usage. Moreover, although the proposed technique does not guarantee the derivation of an alignment with minimal cost, the experiments show that in practice the quality of the obtained solutions is close to optimal., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed, Postprint (author's final draft)
- Published
- 2020
22. Computing Alignments of Well-Formed Process Models using Local Search
- Author
-
Taymouri, Farbod, primary and Carmona, Josep, additional
- Published
- 2020
- Full Text
- View/download PDF
23. Structural computation of alignments of business processes over partial orders
- Author
-
Universitat Politècnica de Catalunya. Doctorat en Computació, Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals, Taymouri, Farbod, Carmona Vargas, Josep, Universitat Politècnica de Catalunya. Doctorat en Computació, Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals, Taymouri, Farbod, and Carmona Vargas, Josep
- Abstract
Relating event data and process models is becoming an important element for organizations. This paper presents a novel approach for aligning traces and process models. The approach is based on the structural theory of Petri nets (the marking equation), applied over an unfolding of the initial process model. Given an observed trace, the approach adopts an iterative optimization mechanism on top of the unfolding, computing at each iteration part of the resulting alignment. In contrast to the previous work that is primarily grounded in the marking equation, this approach is guaranteed to provide real solutions, and tries to mimic as much as possible the events observed in the trace. Experiments witness the significance of this approach both in quality and execution time perspectives., Peer Reviewed, Postprint (author's final draft)
- Published
- 2019
24. Light methods for conformance checking of business processes
- Author
-
Taymouri, Farbod, Carmona Vargas, Josep, and Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
- Subjects
Informàtica [Àrees temàtiques de la UPC] ,Computing ,Process mining ,Data science - Abstract
Conformance Checking is a new research discipline devoted to identify deviations between business process models and their real executions. Identifying deviations boils down to the notion of alignment conceptually. An alignment quantifies to what degree a process model can imitate what happened in its observed behavior, i.e., an event log. Accordingly, an optimal alignment is the best combination by which the process model can imitate the corresponding observed behavior. The state of the art technique for alignment computation has exponential time and space complexity, hindering its applicability for medium and large instances. The main aim of this thesis is to propose light and efficient methods for alignment computation. By finding a suitable trade-off between computation time, memory consumption and optimality, a familly of techniques is proposed such that depending on the input assumptions and required guarantees, a user can select the right technique for her particular problem. Generally speaking, the methods presented in this thesis can be categorized as: - Classical approaches: These techniques exploit Integer Linear Programming (ILP), as well as structural theory of Petri nets, to formulate alignment computation as an optimization of a set of linear equations. A modification to this strategy which trades-off between complexity and quality is to integrate it with state of the art approach. - Heuristic approaches: These techniques take advantages of heuristic functions to explore the search space of alignments, to find the optimal one(s). This can be done by obtaining an initial solution, and iteratively improving it until saturation or reaching a certain criterion. Another contribution is by adopting a Genetic Algorithm with well specific designed operators, by which exploration of the corresponding search space can be speed up toward the best solution(s). - Model reduction: An alternative way to boost the effectiveness of alignment computation is by reducing model and observed behavior without loosing alignment information. This structure reduction not only boosts the alignment computation, but also provides a big picture of detected deviations. Above that, a divide-and-conquer strategy will be provided for the ILP approach, such that it breaks the original problem into a set of smaller independent problems that can be solved independently. Experiments witness the merit of proposed approaches with respect to state of the art technique in different perspectives, such as resource consumption, execution time, quality and accuracy of the solutions found. All methods have been implemented as a stand-alone tool box called ALI. Conformance checking és una nova disciplina dedicada a identificar desviacions entre els models de processos de negoci i les seves execucions reals. Identificar les desviacions porta directament al concepte d'alineament. Un alineament quantifica el grau en que un model de procés pot imitar el que va passar en el seu comportament observat, és a dir, un registre d'esdeveniments. En conseqüència, una alineament òptim és la millor combinació per la qual el model de procés pot imitar el comportament observat. La tècnica de referència per a la computació d'alineaments té una complexitat exponencial, el que dificulta la seva aplicabilitat per a casos mitjans o grans. L'objectiu principal d'aquesta tesi és proposar mètodes eficients per a la computació d'alineaments. En trobar un punt raonable entre el temps d'execució, el consum de memòria i la optimalitat, es proposa una família de tècniques de manera que, segons els supòsits d'entrada i les garanties requerides, un usuari pot seleccionar la tècnica adequada per al seu problema. En termes generals, els mètodes presentats en aquesta tesi es poden classificar com: Enfocaments clàssics: aquestes tècniques utilitzen la Programació Lineal Entera (anglès, ILP), així com la teoria estructural de les xarxes Petri, per realitzar la computació d'alineaments com una optimització d'un conjunt d'equacions lineals. Una modificació d'aquesta estratègia, que pondera la complexitat i la qualitat, és la d'integrar-la amb l'enfocament de referència. Aproximacions heurístiques: aquestes tècniques aprofiten funcions heurístiques per explorar l'espai de cerca d'alineaments, per trobar les solucions properes a l'òptim. Això es pot fer obtenint una solució inicial, que es millorarà iterativament fins a la saturació, o bé assolint un criteri determinat de convergència. Una altra contribució és l'adopció d'un algoritme evolutiu amb operadors específics, que permeten guiar l'exploració de l'espai de cerca corresponent cap a les millors solucions. Reducció de models: una forma alternativa de potenciar l'efectivitat de la computació d'alineaments és reduint el comportament modelat i observat sense perdre la informació d'alineaments. Aquesta reducció d'estructura no només alleugereix el problema, sinó que també proporciona una visió abstracta de les desviacions detectades. Addicionalment, es proposa una estratègia de divideix i vèncer per a l'enfocament de l'ILP, que trenca el problema original en un conjunt de problemes independents més petits que es poden resoldre de forma independent. Els experiments realitzats per cada tècnica demostren la capacitat dels algorismes proposats, en diferents perspectives, com ara el consum de recursos, el temps d'execució, la qualitat i la precisió de les solucions trobades. Tots els mètodes s'han implementat en el software open-source ALI.
- Published
- 2018
25. Structural Computation of Alignments of Business Processes Over Partial Orders
- Author
-
Taymouri, Farbod, primary and Carmona, Josep, additional
- Published
- 2019
- Full Text
- View/download PDF
26. An evolutionary technique to approximate multiple optimal alignments
- Author
-
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals, Taymouri, Farbod, Carmona Vargas, Josep, Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals, Taymouri, Farbod, and Carmona Vargas, Josep
- Abstract
The alignment of observed and modeled behavior is an essential aid for organizations, since it opens the door for root-cause analysis and enhancement of processes. The state-of-the-art technique for computing alignments has exponential time and space complexity, hindering its applicability for medium and large instances. Moreover, the fact that there may be multiple optimal alignments is perceived as a negative situation, while in reality it may provide a more comprehensive picture of the model’s explanation of observed behavior, from which other techniques may benefit. This paper presents a novel evolutionary technique for approximating multiple optimal alignments. Remarkably, the memory footprint of the proposed technique is bounded, representing an unprecedented guarantee with respect to the state-of-the-art methods for the same task. The technique is implemented into a tool, and experiments on several benchmarks are provided., Peer Reviewed, Postprint (author's final draft)
- Published
- 2018
27. Light methods for conformance checking of business processes
- Author
-
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Carmona Vargas, Josep, Taymouri, Farbod, Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Carmona Vargas, Josep, and Taymouri, Farbod
- Abstract
Conformance Checking is a new research discipline devoted to identify deviations between business process models and their real executions. Identifying deviations boils down to the notion of alignment conceptually. An alignment quantifies to what degree a process model can imitate what happened in its observed behavior, i.e., an event log. Accordingly, an optimal alignment is the best combination by which the process model can imitate the corresponding observed behavior. The state of the art technique for alignment computation has exponential time and space complexity, hindering its applicability for medium and large instances. The main aim of this thesis is to propose light and efficient methods for alignment computation. By finding a suitable trade-off between computation time, memory consumption and optimality, a familly of techniques is proposed such that depending on the input assumptions and required guarantees, a user can select the right technique for her particular problem. Generally speaking, the methods presented in this thesis can be categorized as: - Classical approaches: These techniques exploit Integer Linear Programming (ILP), as well as structural theory of Petri nets, to formulate alignment computation as an optimization of a set of linear equations. A modification to this strategy which trades-off between complexity and quality is to integrate it with state of the art approach. - Heuristic approaches: These techniques take advantages of heuristic functions to explore the search space of alignments, to find the optimal one(s). This can be done by obtaining an initial solution, and iteratively improving it until saturation or reaching a certain criterion. Another contribution is by adopting a Genetic Algorithm with well specific designed operators, by which exploration of the corresponding search space can be speed up toward the best solution(s). - Model reduction: An alternative way to boost the effectiveness of alignment computation is by reducing, Conformance checking és una nova disciplina dedicada a identificar desviacions entre els models de processos de negoci i les seves execucions reals. Identificar les desviacions porta directament al concepte d'alineament. Un alineament quantifica el grau en que un model de procés pot imitar el que va passar en el seu comportament observat, és a dir, un registre d'esdeveniments. En conseqüència, una alineament òptim és la millor combinació per la qual el model de procés pot imitar el comportament observat. La tècnica de referència per a la computació d'alineaments té una complexitat exponencial, el que dificulta la seva aplicabilitat per a casos mitjans o grans. L'objectiu principal d'aquesta tesi és proposar mètodes eficients per a la computació d'alineaments. En trobar un punt raonable entre el temps d'execució, el consum de memòria i la optimalitat, es proposa una família de tècniques de manera que, segons els supòsits d'entrada i les garanties requerides, un usuari pot seleccionar la tècnica adequada per al seu problema. En termes generals, els mètodes presentats en aquesta tesi es poden classificar com: Enfocaments clàssics: aquestes tècniques utilitzen la Programació Lineal Entera (anglès, ILP), així com la teoria estructural de les xarxes Petri, per realitzar la computació d'alineaments com una optimització d'un conjunt d'equacions lineals. Una modificació d'aquesta estratègia, que pondera la complexitat i la qualitat, és la d'integrar-la amb l'enfocament de referència. Aproximacions heurístiques: aquestes tècniques aprofiten funcions heurístiques per explorar l'espai de cerca d'alineaments, per trobar les solucions properes a l'òptim. Això es pot fer obtenint una solució inicial, que es millorarà iterativament fins a la saturació, o bé assolint un criteri determinat de convergència. Una altra contribució és l'adopció d'un algoritme evolutiu amb operadors específics, que permeten guiar l'exploració de l'espai de cerca corresponent cap a les millors solucions. R, Postprint (published version)
- Published
- 2018
28. Aligning Modeled and Observed Behavior: A Compromise Between Complexity and Quality
- Author
-
Van Dongen, Boudewijn, Carmona, Josep, Chatain, Thomas, Taymouri, Farbod, Eindhoven University of Technology [Eindhoven] (TU/e), Universitat Politècnica de Catalunya [Barcelona] (UPC), Laboratoire Spécification et Vérification [Cachan] (LSV), École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS), Modeling and Exploitation of Interaction and Concurrency (MEXICO), École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
- Subjects
ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES ,[INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] - Abstract
International audience; Certifying that a process model is aligned with the real process executions is perhaps the most desired feature a process model may have: aligned process models are crucial for organizations, since strategic decisions can be made easier on models instead of on plain data. In spite of its importance, the current algorithmic support for computing alignments is limited: either techniques that explicitly explore the model behavior (which may be worst-case exponential with respect to the model size), or heuristic approaches that cannot guarantee a solution, are the only alternatives. In this paper we propose a solution that sits right in the middle in the complexity spectrum of alignment techniques; it can always guarantee a solution, whose quality depends on the exploration depth used and local decisions taken at each step. We use linear algebraic techniques in combination with an iterative search which focuses on progressing towards a solution. The experiments show a clear reduction in the time required for reaching a solution, without sacrificing significantly the quality of the alignment obtained.
- Published
- 2017
29. Aligning modeled and observed behavior: A compromise between computation complexity and quality
- Author
-
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals, Dongen, Boudewijn F. van, Carmona Vargas, Josep, Chatain, Thomas, Taymouri, Farbod, Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals, Dongen, Boudewijn F. van, Carmona Vargas, Josep, Chatain, Thomas, and Taymouri, Farbod
- Abstract
Certifying that a process model is aligned with the real process executions is perhaps the most desired feature a process model may have: aligned process models are crucial for organizations, since strategic decisions can be made easier on models instead of on plain data. In spite of its importance, the current algorithmic support for computing alignments is limited: either techniques that explicitly explore the model behavior (which may be worst-case exponential with respect to the model size), or heuristic approaches that cannot guarantee a solution, are the only alternatives. In this paper we propose a solution that sits right in the middle in the complexity spectrum of alignment techniques; it can always guarantee a solution, whose quality depends on the exploration depth used and local decisions taken at each step. We use linear algebraic techniques in combination with an iterative search which focuses on progressing towards a solution. The experiments show a clear reduction in the time required for reaching a solution, without sacrificing significantly the quality of the alignment obtained., Peer Reviewed, Postprint (author's final draft)
- Published
- 2017
30. A recursive paradigm for aligning observed behavior of large structured process models
- Author
-
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals, Taymouri, Farbod, Carmona Vargas, Josep, Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals, Taymouri, Farbod, and Carmona Vargas, Josep
- Abstract
The alignment of observed and modeled behavior is a crucial problem in process mining, since it opens the door for conformance checking and enhancement of process models. The state of the art techniques for the computation of alignments rely on a full exploration of the combination of the model state space and the observed behavior (an event log), which hampers their applicability for large instances. This paper presents a fresh view to the alignment problem: the computation of alignments is casted as the resolution of Integer Linear Programming models, where the user can decide the granularity of the alignment steps. Moreover, a novel recursive strategy is used to split the problem into small pieces, exponentially reducing the complexity of the ILP models to be solved. The contributions of this paper represent a promising alternative to fight the inherent complexity of computing alignments for large instances., Peer Reviewed, Postprint (author's final draft)
- Published
- 2016
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.