[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
survey

Probabilistic Complex Event Recognition: A Survey

Published: 26 September 2017 Publication History

Abstract

Complex event recognition (CER) applications exhibit various types of uncertainty, ranging from incomplete and erroneous data streams to imperfect complex event patterns. We review CER techniques that handle, to some extent, uncertainty. We examine techniques based on automata, probabilistic graphical models, and first-order logic, which are the most common ones, and approaches based on Petri nets and grammars, which are less frequently used. Several limitations are identified with respect to the employed languages, their probabilistic models, and their performance, as compared to the purely deterministic cases. Based on those limitations, we highlight promising directions for future work.

References

[1]
J. Agrawal, Y. Diao, D. Gyllstrom, and N. Immerman. 2008. Efficient pattern matching over event streams. In Proceedings of SIGMOD. 147--160.
[2]
M. Albanese, R. Chellappa, N. Cuntoor, V. Moscato, A. Picariello, V. S. Subrahmanian, and O. Udrea. 2010. PADS: A probabilistic activity detection framework for video data. IEEE Transactions on Pattern Analysis and Machine Intelligence 32, 12, 2246--2261.
[3]
M. Albanese, R. Chellappa, N. P. Cuntoor, V. Moscato, A. Picariello, V. S. Subrahmanian, and O. Udrea. 2008. A constrained probabilistic Petri net framework for human activity detection in video. IEEE Transactions on Multimedia 10, 6, 982--996.
[4]
M. Albanese, C. Molinaro, F. Persia, A. Picariello, and V. S. Subrahmanian. 2011. Finding “unexplained” activities in video. In Proceedings of IJCAI. 1628--1634.
[5]
M. Albanese, V. Moscato, A. Picariello, V. S. Subrahmanian, and O. Udrea. 2007. Detecting stochastically scheduled activities in video. In Proceedings of IJCAI. 1802--1807.
[6]
James F. Allen. 1983. Maintaining knowledge about temporal intervals. Communications of the ACM 26, 11, 832--843.
[7]
James F. Allen. 1984. Towards a general theory of action and time. Artificial Intelligence 23, 2, 123--154.
[8]
Alexander Artikis, Opher Etzion, Zohar Feldman, and Fabiana Fournier. 2012. Event processing under uncertainty. In Proceedings of DEBS. ACM, New York, NY, 32--43.
[9]
Alexander Artikis, Marek Sergot, and Georgios Paliouras. 2010. A logic programming approach to activity recognition. In Proceedings of EiMM. ACM, New York, NY, 3--8.
[10]
Alexander Artikis, Marek Sergot, and Georgios Paliouras. 2015. An event calculus for event recognition. IEEE Transactions on Knowledge and Data Engineering 27, 4, 895--908.
[11]
Alexander Artikis, Anastasios Skarlatidis, François Portet, and Georgios Paliouras. 2012. Logic-based event recognition. Knowledge Engineering Review 27, 4, 469--506.
[12]
Omar Benjelloun, Anish Das Sarma, Alon Halevy, and Jennifer Widom. 2006. ULDBs: Databases with uncertainty and lineage. In Proceedings of VLDB. 953--964.
[13]
Hendrik Blockeel and Werner Uwents. 2004. Using neural networks for relational learning. In Proceedings of ICML. 23--28.
[14]
Matthew Brand, Nuria Oliver, and Alex Pentland. 1997. Coupled hidden Markov models for complex action recognition. In Proceedings of CVPR. IEEE, Los Alamitos, CA, 994--999.
[15]
William Brendel, Alan Fern, and Sinisa Todorovic. 2011. Probabilistic event logic for interval-based event recognition. In Proceedings of CVPR. IEEE, Los Alamitos, CA, 3329--3336.
[16]
Maurice Bruynooghe, Broes De Cat, Jochen Drijkoningen, Daan Fierens, Jan Goos, Bernd Gutmann, Angelika Kimmig, et al. 2009. An Exercise With Statistical Relational Learning Systems. Available at https://lirias.kuleuven.be/bitstream/123456789/230569/1/srl
[17]
I. Cervesato and A. Montanari. 2000. A calculus of macro-events: Progress report. In Proceedings of TIME. 47--58.
[18]
Xu Chuanfei, Lin Shukuan, Wang Lei, and Qiao Jianzhong. 2010. Complex event detection in probabilistic stream. In Proceedings of APWEB. 361--363.
[19]
G. Cugola and A. Margara. 2010. TESLA: A formally defined event specification language. In Proceedings of DEBS. 50--61.
[20]
G. Cugola and A. Margara. 2011. Processing flows of information: From data stream to complex event processing. ACM Computing Surveys 44, 3, Article No. 15.
[21]
Gianpaolo Cugola, Alessandro Margara, Matteo Matteucci, and Giordano Tamburrelli. 2014. Introducing uncertainty in complex event processing: Model, implementation, and validation. Computing 97, 2, 103--144.
[22]
Luc De Raedt and Kristian Kersting. 2003. Probabilistic logic learning. ACM SIGKDD Explorations Newsletter 5, 1, 31--48.
[23]
Alan Demers, Johannes Gehrke, Mingsheng Hong, Mirek Riedewald, and Walker White. 2006. Towards expressive publish/subscribe systems. In Proceedings of EDBT. 627--644.
[24]
Pedro Domingos and Daniel Lowd. 2009. Markov Logic: An Interface Layer for Artificial Intelligence. Morgan 8 Claypool.
[25]
Yagil Engel and Opher Etzion. 2011. Towards proactive event-driven computing. In Proceedings of DEBS. 125--136.
[26]
Opher Etzion and Peter Niblett. 2010. Event Processing in Action. Manning Publications, Greenwich, CT.
[27]
Ronald Fagin. 1996. Combining fuzzy information from multiple systems. In Proceedings of PODS. ACM, New York, NY, 216--226.
[28]
Lina Fahed, Armelle Brun, and Anne Boyer. 2014. Efficient discovery of episode rules with a minimal antecedent and a distant consequent. In Knowledge Discovery, Knowledge Engineering and Knowledge Management. Springer, 3--18.
[29]
Daan Fierens, Guy Van den Broeck, Joris Renkens, Dimitar Shterionov, Bernd Gutmann, Ingo Thon, Gerda Janssens, and Luc De Raedt. 2013. Inference and learning in probabilistic logic programs using weighted Boolean formulas. In Proceedings of TPLP. 1--44.
[30]
Norbert Fuhr and Thomas Rölleke. 1997. A probabilistic relational algebra for the integration of information retrieval and database systems. ACM Transactions on Information Systems 15, 1, 32--66.
[31]
Lajos Jenő Fülöp, árpád Beszédes, Gabriella Tóth, Hunor Demeter, László Vidács, and Lóránt Farkas. 2012. Predictive complex event processing: A conceptual framework for combining complex event processing and predictive analytics. In Proceedings of BCI. ACM, New York, NY. 26--31.
[32]
Lise Getoor and Ben Taskar. 2007. Introduction to Statistical Relational Learning. MIT Press, Cambridge, MA.
[33]
Matthew L. Ginsberg. 1988. Multivalued logics: A uniform approach to reasoning in artificial intelligence. Computational Intelligence 4, 265--316.
[34]
Shaogang Gong and Tao Xiang. 2003. Recognition of group activities using dynamic probabilistic networks. In Proceedings of ICCV, Vol. 2. IEEE, Los Alamitos, CA, 742--749.
[35]
Samitha Herath, Mehrtash Harandi, and Fatih Porikli. 2017. Going deeper into action recognition: A survey. Image and Vision Computing 60, C, 4--21.
[36]
Y. A. Ivanov and A. F. Bobick. 2000. Recognition of visual activities and interactions by stochastic parsing. IEEE Transactions on Pattern Analysis and Machine Intelligence 22, 8, 852--872.
[37]
Manfred Jaeger. 1997. Relational Bayesian networks. In Proceedings of UAI. 266--273.
[38]
Manfred Jaeger. 2008. Model-theoretic expressivity analysis. In Probabilistic Inductive Logic Programming. Lecture Notes in Computer Science, Vol. 4911. Springer, 325--339.
[39]
Henry Kautz, Bart Selman, and Yueyen Jiang. 1997. A general stochastic approach to solving problems with hard and soft constraints. In The Satisfiability Problem: Theory and Applications. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 35. American Mathematical Society, 573--586.
[40]
H. Kawashima, H. Kitagawa, and X. Li. 2010. Complex event processing over uncertain data streams. In Proceedings of 3PGCIC. 521--526.
[41]
Kristian Kersting, Luc De Raedt, and Tapani Raiko. 2006. Logical hidden Markov models. Journal of Artificial Intelligence Research 25, 1, 2006, 425--456.
[42]
S. Khokhar, I. Saleemi, and M. Shah. 2013. Multi-agent event recognition by preservation of spatiotemporal relationships between probabilistic models. Image and Vision Computing 31, 9, 603--615.
[43]
A. Kimmig, B. Demoen, L. De Raedt, V. Santos Costa, and R. Rocha. 2011. On the implementation of the probabilistic logic programming language problog. Theory and Practice of Logic Programming 11, 2--3, 235--262.
[44]
Robert Kowalski and Marek Sergot. 1986. A logic-based calculus of events. New Generation Computing 4, 1, 67--95.
[45]
John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of ICML. 282--289.
[46]
G. Lavee, M. Rudzsky, and E. Rivlin. 2013. Propagating certainty in Petri nets for activity recognition. IEEE Transactions on Circuits and Systems for Video Technology 23, 2, 326--337.
[47]
Srivatsan Laxman and P. Shanti Sastry. 2006. A survey of temporal data mining. Sadhana 31, 2, 173--198.
[48]
Srivatsan Laxman, Vikram Tankasali, and Ryen W. White. 2008. Stream prediction using a generative model based on frequent episodes in event sequences. In Proceedings of KDD. 453--461.
[49]
Lin Liao, Dieter Fox, and Henry A. Kautz. 2005. Hierarchical conditional random fields for GPS-based activity recognition. In Proceedings of ISRR, 487--506.
[50]
David C. Luckham. 2001. The Power of Events: An Introduction to Complex Event Processing in Distributed Enterprise Systems. Addison-Wesley.
[51]
Jianbing Ma, Weiru Liu, and Paul Miller. 2010. Event modelling and reasoning with uncertain information for distributed sensor networks. In Scalable Uncertainty Management. Springer, 236--249.
[52]
Cristina Manfredotti. 2009. Modeling and inference with relational dynamic Bayesian networks. In Advances in Artificial Intelligence. Lecture Notes in Computer Science, Vol. 5549. Springer, 287--290.
[53]
Cristina Manfredotti, Howard Hamilton, and Sandra Zilles. 2010. Learning RDBNs for activity recognition. In Proceedings of NIPS.
[54]
Marcelo R. N. Mendes, Pedro Bizarro, and Paulo Marques. 2009. A performance study of event processing systems. In Performance Evaluation and Benchmarking. Lecture Notes in Computer Science, Vol. 5895. Springer, 221--236.
[55]
Marcelo R. N. Mendes, Pedro Bizarro, and Paulo Marques. 2013. Towards a standard event processing benchmark. In Proceedings of ICPE. ACM, New York, NY, 307--310.
[56]
D. Minnen, I. Essa, and T. Starner. 2003. Expectation grammars: Leveraging high-level expectations for activity recognition. In Proceedings of CVPR, Vol. 2. 626--632.
[57]
C. Molinaro, V. Moscato, A. Picariello, A. Pugliese, A. Rullo, and V. S. Subrahmanian. 2014. PADUA: Parallel architecture to detect unexplained activities. ACM Transactions on Internet Technology 14, 1, Article No. 3.
[58]
Darnell Moore and Irfan Essa. 2002. Recognizing multitasked activities from video using stochastic context-free grammar. In Proceedings of AAAI/IAAI. 770--776.
[59]
Vlad I. Morariu and Larry S. Davis. 2011. Multi-agent event recognition in structured scenarios. In Proceedings of CVPR. 3289--3296.
[60]
Stephen Muggleton and Jianzhong Chen. 2008. A behavioral comparison of some probabilistic logic models. In Probabilistic Inductive Logic Programming. Lecture Notes in Computer Science, Vol. 4911. Springer, 305--324.
[61]
T. Murata. 1989. Petri nets: Properties, analysis and applications. Proceedings of the IEEE 77, 4, 541--580.
[62]
Kevin P. Murphy. 2002. Dynamic Bayesian Networks: Representation, Inference and Learning. Ph.D. Dissertation. University of California.
[63]
Adrian Paschke. 2006. ECA-RuleML: An approach combining ECA rules with temporal interval-based KR event/action logics and transactional update logics. arXiv:cs/0610167.
[64]
Adrian Paschke and Martin Bichler. 2008. Knowledge representation concepts for automated SLA management. Decision Support Systems 46, 1, 187--205.
[65]
Mingtao Pei, Zhangzhang Si, Benjamin Z. Yao, and Song-Chun Zhu. 2013. Learning and parsing video events with goal and intent prediction. Computer Vision and Image Understanding 117, 10, 1369--1383.
[66]
James Lyle Peterson. 1981. Petri Net Theory and the Modeling of Systems. Prentice Hall.
[67]
Lawrence R. Rabiner and Biing-Hwang Juang. 1986. An introduction to hidden Markov models. ASSP Magazine 3, 1, 4--16.
[68]
Christopher Ré, Julie Letchner, Magdalena Balazinksa, and Dan Suciu. 2008. Event queries on correlated probabilistic streams. In Proceedings of SIGMOD. 715--728.
[69]
M. Richardson and P. Domingos. 2006. Markov logic networks. Machine Learning 62, 1--2, 107--136.
[70]
Michael S. Ryoo and Jake K. Aggarwal. 2006. Recognition of composite human activities through context-free grammar based representation. In Proceedings of CVPR. 1709--1718.
[71]
Michael S. Ryoo and Jake K. Aggarwal. 2009. Semantic representation and recognition of continued and recursive human activities. International Journal of Computer Vision 82, 1, 1--24.
[72]
Sumit Sanghai, Pedro Domingos, and Daniel Weld. 2005. Relational dynamic Bayesian networks. Journal of Artificial Intelligence Research 24, 2005, 759--797.
[73]
Joseph Selman, Mohamed R. Amer, Alan Fern, and Sinisa Todorovic. 2011. PEL-CNF: Probabilistic event logic conjunctive normal form for video interpretation. In Proceedings of ICCVW. IEEE, Los Alamitos, CA, 680--687.
[74]
Zhitao Shen, Hideyuki Kawashima, and Hiroyuki Kitagawa. 2008. Lineage-based probabilistic event stream processing. In Proceedings of MDMW. 106--113.
[75]
Vinay D. Shet, Jan Neumann, Visvanathan Ramesh, and Larry S. Davis. 2007. Bilattice-based logical reasoning for human detection. In Proceedings of CVPR. IEEE, Los Alamitos, CA, 1--8.
[76]
Vinay D. Shet, Maneesh Singh, Claus Bahlmann, Visvanathan Ramesh, Jan Neumann, and Larry S. Davis. 2011. Predicate logic based image grammars for complex pattern recognition. International Journal of Computer Vision 93, 2, 141--161.
[77]
Jeffrey Mark Siskind. 2001. Grounding the lexical semantics of verbs in visual perception using force dynamics and event logic. Journal of Artificial Intelligence Research 15, 2001, 31--90.
[78]
Anastasios Skarlatidis, Alexander Artikis, Jason Filippou, and Georgios Paliouras. 2013. A probabilistic logic programming event calculus. Theory and Practice of Logic Programming 15, 2, 213--245.
[79]
Anastasios Skarlatidis, Georgios Paliouras, Alexander Artikis, and George A. Vouros. 2015. Probabilistic event calculus for event recognition. ACM Transactions on Computational Logic 16, 2, Article No. 11.
[80]
Anastaios Skarlatidis, Georgios Paliouras, George Vouros, and Alexander Artikis. 2011. Probabilistic event calculus based on Markov logic networks. In Rule-Based Modeling and Computing on the Semantic Web. Lecture Notes in Computer Science, Vol. 7018. Springer, 155--170.
[81]
Young Chol Song, Henry Kautz, James Allen, Mary Swift, Yuncheng Li, Jiebo Luo, and Ce Zhang. 2013. A Markov logic framework for recognizing complex events from multimodal data. In Proceedings of ICMI. 141--148.
[82]
Young Chol Song, Henry A. Kautz, Yuncheng Li, and Jiebo Luo. 2013. A general framework for recognizing complex events in Markov logic. In Proceedings of AAAIWS. 68--73.
[83]
Gustav Šourek, Vojtech Aschenbrenner, Filip Železny, and Ondřej Kuželka. 2015. Lifted relational neural networks. In Proceedings of COCO. 52--60.
[84]
Andreas Stolcke. 1995. An efficient probabilistic context-free parsing algorithm that computes prefix probabilities. Computational Linguistics 21, 2, 165--201.
[85]
Son Dinh Tran and Larry S. Davis. 2008. Event modeling and recognition using Markov logic networks. In Proceedings of ECCV, Vol. 5303. 610--623.
[86]
Douglas L. Vail, Manuela M. Veloso, and John D. Lafferty. 2007. Conditional random fields for activity recognition. In Proceedings of AAMAS. 1331--1338.
[87]
Sarvesh Vishwakarma and Anupam Agrawal. 2013. A survey on activity recognition and behavior understanding in video surveillance. Visual Computer 29, 10, 983--1009.
[88]
Yijie Wang, Xiaoyong Li, Xiaoling Li, and Yuan Wang. 2013. A survey of queries over uncertain data. Knowledge and Information Systems 37, 3, 485--530.
[89]
Y. H. Wang, K. Cao, and X. M. Zhang. 2013. Complex event processing over distributed probabilistic event streams. Computers and Mathematics With Applications 66, 10, 1808--1821.
[90]
Segev Wasserkrug, Avigdor Gal, and Opher Etzion. 2006. A taxonomy and representation of sources of uncertainty in active systems. In Next Generation Information Technologies and Systems. Lecture Notes in Computer Science, Vol. 4032. Springer, 174--185.
[91]
Segev Wasserkrug, Avigdor Gal, and Opher Etzion. 2012. A model for reasoning with uncertain rules in event composition systems. arXiv:1207.1427/[cs]
[92]
Segev Wasserkrug, Avigdor Gal, Opher Etzion, and Yulia Turchin. 2008. Complex event processing over uncertain data. In Proceedings of DEBS. ACM, New York, NY, 253--264.
[93]
Segev Wasserkrug, Avigdor Gal, Opher Etzion, and Yulia Turchin. 2012. Efficient processing of uncertain events in rule-based systems. IEEE Transactions on Knowledge and Data Engineering 24, 1, 45--58.
[94]
Eugene Wu, Yanlei Diao, and Shariq Rizvi. 2006. High-performance complex event processing over streams. In Proceedings of SIGMOD. 407--418.
[95]
Tsu-Yu Wu, Chia-Chun Lian, and Jane Yung-Jen Hsu. 2007. Joint recognition of multiple concurrent activities using factorial conditional random fields. In Proceedings of PAIR. 82--88.
[96]
Haopeng Zhang, Yanlei Diao, and Neil Immerman. 2010. Recognizing patterns in streams with imprecise timestamps. Proceedings of the VLDB Endowment 3, 1--2, 244--255.
[97]
Haopeng Zhang, Yanlei Diao, and Neil Immerman. 2014. On complexity and optimization of expensive queries in complex event processing. In Proceedings of SIGMOD. 217--228.
[98]
Cheng Zhou, Boris Cule, and Bart Goethals. 2015. A pattern based predictor for event streams. Expert Systems With Applications 42, 23, 9294--9306.
[99]
Song-Chun Zhu and David Mumford. 2007. A stochastic grammar of images. Foundations and Trends in Computer Graphics and Vision 2, 4, 259--362.

Cited By

View all
  • (2024)Human activity recognition: A comprehensive reviewExpert Systems10.1111/exsy.1368041:11Online publication date: 27-Jul-2024
  • (2024) Rule based complex event processing for IoT applications: Review, classification and challenges Expert Systems10.1111/exsy.13597Online publication date: 30-Mar-2024
  • (2024)»Relationships are Key« A Semantic Relationship Awareness Framework for Operational Technology MonitoringSN Computer Science10.1007/s42979-024-03071-15:6Online publication date: 8-Aug-2024
  • Show More Cited By

Index Terms

  1. Probabilistic Complex Event Recognition: A Survey

                                  Recommendations

                                  Comments

                                  Please enable JavaScript to view thecomments powered by Disqus.

                                  Information & Contributors

                                  Information

                                  Published In

                                  cover image ACM Computing Surveys
                                  ACM Computing Surveys  Volume 50, Issue 5
                                  September 2018
                                  573 pages
                                  ISSN:0360-0300
                                  EISSN:1557-7341
                                  DOI:10.1145/3145473
                                  • Editor:
                                  • Sartaj Sahni
                                  Issue’s Table of Contents
                                  © 2017 Association for Computing Machinery. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

                                  Publisher

                                  Association for Computing Machinery

                                  New York, NY, United States

                                  Publication History

                                  Published: 26 September 2017
                                  Accepted: 01 June 2017
                                  Revised: 01 April 2017
                                  Received: 01 July 2016
                                  Published in CSUR Volume 50, Issue 5

                                  Permissions

                                  Request permissions for this article.

                                  Check for updates

                                  Author Tags

                                  1. Event processing
                                  2. probabilistic Petri nets
                                  3. probabilistic automata
                                  4. probabilistic graphical models
                                  5. probabilistic logics
                                  6. stochastic grammars
                                  7. uncertainty

                                  Qualifiers

                                  • Survey
                                  • Research
                                  • Refereed

                                  Funding Sources

                                  • EU H2020 datACRON and EU FP7 SPEEDD projects

                                  Contributors

                                  Other Metrics

                                  Bibliometrics & Citations

                                  Bibliometrics

                                  Article Metrics

                                  • Downloads (Last 12 months)50
                                  • Downloads (Last 6 weeks)4
                                  Reflects downloads up to 16 Jan 2025

                                  Other Metrics

                                  Citations

                                  Cited By

                                  View all
                                  • (2024)Human activity recognition: A comprehensive reviewExpert Systems10.1111/exsy.1368041:11Online publication date: 27-Jul-2024
                                  • (2024) Rule based complex event processing for IoT applications: Review, classification and challenges Expert Systems10.1111/exsy.13597Online publication date: 30-Mar-2024
                                  • (2024)»Relationships are Key« A Semantic Relationship Awareness Framework for Operational Technology MonitoringSN Computer Science10.1007/s42979-024-03071-15:6Online publication date: 8-Aug-2024
                                  • (2024)Complex event recognition and anomaly detection with event behavior modelPattern Analysis & Applications10.1007/s10044-024-01275-y27:2Online publication date: 30-Apr-2024
                                  • (2024)Programming Approaches for Large-Scale IoT System Development: State of the ArtFluidware10.1007/978-3-031-62146-8_2(21-45)Online publication date: 13-May-2024
                                  • (2023)Incremental event calculus for run-time reasoning (extended abstract)Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/793(6974-6978)Online publication date: 19-Aug-2023
                                  • (2023)Online event recognition over noisy data streamsInternational Journal of Approximate Reasoning10.1016/j.ijar.2023.108993161(108993)Online publication date: Oct-2023
                                  • (2023)DeepProbCEPExpert Systems with Applications: An International Journal10.1016/j.eswa.2022.119376215:COnline publication date: 15-Feb-2023
                                  • (2022)COREProceedings of the VLDB Endowment10.14778/3538598.353861515:9(1951-1964)Online publication date: 27-Jul-2022
                                  • (2022)Optimizing vessel trajectory compression for maritime situational awarenessGeoInformatica10.1007/s10707-022-00475-027:3(565-591)Online publication date: 29-Aug-2022
                                  • Show More Cited By

                                  View Options

                                  Login options

                                  Full Access

                                  View options

                                  PDF

                                  View or Download as a PDF file.

                                  PDF

                                  eReader

                                  View online with eReader.

                                  eReader

                                  Media

                                  Figures

                                  Other

                                  Tables

                                  Share

                                  Share

                                  Share this Publication link

                                  Share on social media