Probabilistic Complex Event Recognition: A Survey

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.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Knowledge representation and reasoning

      • Probabilistic reasoning

• General and reference

  • Document types

    • Surveys and overviews

• Information systems

  • Data management systems

    • Database design and models

      • Data model extensions

        • Data streams

        • Temporal data

        • Uncertainty

• Mathematics of computing

  • Probability and statistics

    • Probabilistic algorithms

    • Probabilistic inference problems

    • Probabilistic representations

      • Bayesian networks

      • Markov networks

    • Stochastic processes

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Real-time systems software

      • Software system models

        • Petri nets

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis

      • Pattern matching

  • Formal languages and automata theory

    • Grammars and context-free languages

  • Logic

    • Modal and temporal logics

  • Models of computation

    • Probabilistic computation