×

Incremental learning of event definitions with inductive logic programming. (English) Zbl 1341.68159

Summary: Event recognition systems rely on knowledge bases of event definitions to infer occurrences of events in time. Using a logical framework for representing and reasoning about events offers direct connections to machine learning, via Inductive Logic Programming (ILP), thus allowing to avoid the tedious and error-prone task of manual knowledge construction. However, learning temporal logical formalisms, which are typically utilized by logic-based event recognition systems is a challenging task, which most ILP systems cannot fully undertake. In addition, event-based data is usually massive and collected at different times and under various circumstances. Ideally, systems that learn from temporal data should be able to operate in an incremental mode, that is, revise prior constructed knowledge in the face of new evidence. In this work we present an incremental method for learning and revising event-based knowledge, in the form of Event Calculus programs. The proposed algorithm relies on abductive-inductive learning and comprises a scalable clause refinement methodology, based on a compressive summarization of clause coverage in a stream of examples. We present an empirical evaluation of our approach on real and synthetic data from activity recognition and city transport applications.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68N17 Logic programming
68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence

Software:

Subsumer
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Ade, H., & Denecker, M. (1995). AILP: Abductive inductive logic programming. In Proceedings of the international joint conference on artificial intelligence (IJCAI). · Zbl 1179.68125
[2] Alrajeh, D., Kramer, J., Russo, A., & Uchitel, S. (2009). Learning operational requirements from goal models. In Proceedings of the 31st international conference on software engineering (pp. 265-275). IEEE Computer Society.
[3] Alrajeh, D; Kramer, J; Russo, A; Uchitel, S, Deriving non-Zeno behaviour models from goal models using ILP, Formal Aspects of Computing, 22, 217-241, (2010) · Zbl 1213.68360
[4] Alrajeh, D., Kramer, J., Russo, A., & Uchitel, S. (2011). An inductive approach for modal transition system refinement. In Technical communications of the international conference of logic programming ICLP (pp. 106-116). Citeseer. · Zbl 1245.68061
[5] Alrajeh, D., Kramer, J., Russo, A., & Uchitel, S. (2012). Learning from vacuously satisfiable scenario-based specifications. In Proceedings of the international conference on fundamental approaches to software engineering (FASE).
[6] Artikis, A; Skarlatidis, A; Paliouras, G, Behaviour recognition from video content: A logic programming approach, International Journal on Artificial Intelligence Tools, 19, 193-209, (2010)
[7] Artikis, A; Skarlatidis, A; Portet, F; Paliouras, G, Logic-based event recognition, Knowledge Engineering Review, 27, 469-506, (2012)
[8] Artikis, A; Sergot, M; Paliouras, G, An event calculus for event recognition, IEEE Transactions on Knowledge and Data Engineering (TKDE), 27, 895-908, (2015)
[9] Athakravi, D., Corapi, D., Broda, K., & Russo, A. (2013). Learning through hypothesis refinement using answer set programming. In Proceedings of the 23rd international conference of inductive logic programming (ILP). · Zbl 1319.68166
[10] Badea, L. (2001). A refinement operator for theories. In Proceedings of the international conference on inductive logic programming (ILP). · Zbl 1007.68504
[11] Biba, M., Basile, T. M. A., Ferilli, S., & Esposito, F. (2006). Improving scalability in ILP incremental systems. In Proceedings of CILC 2006-Italian conference on computational logic, Bari, Italy, pp. 26-27.
[12] Bragaglia, S. & Ray, O. (2014). Nonmonotonic learning in large biological networks. In Proceedings of the international conference on inductive logic programming (ILP).
[13] Cattafi, M; Lamma, E; Riguzzi, F; Storari, S, Incremental declarative process mining, Smart Information and Knowledge Management, 260, 103-127, (2010)
[14] Cervesato, I., & Montanari, A. (2000). A calculus of macro-events: Progress report. In Proceedings of the international workshop on temporal representation and reasoning (TIME). IEEE.
[15] Chaudet, H, Extending the event calculus for tracking epidemic spread, Artificial Intelligence in Medicine, 38, 137-156, (2006)
[16] Corapi, D., Ray, O., Russo, A., Bandara, A., & Lupu, E. (2008). Learning rules from user behaviour. In Second international workshop on the induction of process models.
[17] Corapi, D., Russo, A., & Lupu, E. (2010). Inductive logic programming as abductive search. In Technical communications of the international conference on logic programming (ICLP). · Zbl 1237.68203
[18] Corapi, D., Russo, A., & Lupu, E. (2012). Inductive logic programming in answer set programming. In Proceedings of international conference on inductive logic programming (ILP). Springer. · Zbl 1237.68203
[19] De Raedt, L., & Bruynooghe, M. (1994). Interactive theory revision. In Machine learning: A multistrategy approach, pp. 239-263.
[20] Denecker, M., & Kakas, A. (2002). Abduction in logic programming. In Computational logic: Logic programming and beyond, pp. 402-436. · Zbl 1012.68503
[21] Di Mauro, N., Esposito, F., Ferilli, S., & Basile, T. M. A. (2004). A backtracking strategy for order-independent incremental learning. In Proceedings of the European conference on artificial intelligence (ECAI). · Zbl 1105.68373
[22] Di Mauro, N., Esposito, F., Ferilli, S., & Basile, T. M. (2005). Avoiding order effects in incremental learning. In AIIA 2005: Advances in artificial intelligence, pp. 110-121. · Zbl 1155.68480
[23] Dietterich, TG; Domingos, P; Getoor, L; Muggleton, S; Tadepalli, P, Structured machine learning: the next ten years, Machine Learning, 73, 3-23, (2008)
[24] Duboc, AL; Paes, A; Zaverucha, G, Using the bottom clause and mode declarations in FOL theory revision from examples, Machine Learning, 76, 73-107, (2009)
[25] Eshghi, K., & Kowalski, R. (1989). Abduction compared with negation by failure. In Proceedings of the 6th international conference on logic programming.
[26] Esposito, F; Semeraro, G; Fanizzi, N; Ferilli, S, Multistrategy theory revision: induction and abduction in inthelex, Machine Learning, 28, 133-156, (2000) · Zbl 0960.68603
[27] Esposito, F; Ferilli, S; Fanizzi, N; Basile, TMA; Mauro, N, Incremental learning and concept drift in inthelex, Intelligent Data Analysis, 8, 213-237, (2004) · Zbl 1168.03318
[28] Etzion, O., & Niblett, P. (2010). Event processing in action. Greenwich: Manning Publications Co.
[29] Gebser, M; Kaminski, R; Kaufmann, B; Schaub, T, Answer set solving in practice, Synthesis Lectures on Artificial Intelligence and Machine Learning, 6, 1-238, (2012)
[30] Gelfond, M., & Lifschitz, V. (1988). The stable model semantics for logic programming. In International conference on logic programming, pp. 1070-1080.
[31] Kakas, A., & Mancarella, P. (1990). Generalised stable models: A semantics for abduction. In Ninth European conference on artificial intelligence (ECAI-90), pp. 385-391.
[32] Kakas, A; Kowalski, R; Toni, F, Abductive logic programming, Journal of Logic and Computation, 2, 719-770, (1993) · Zbl 0778.68081
[33] Kimber, T., Broda, K., & Russo, A. (2009). Induction on failure: Learning connected horn theories. In Logic programming and nonmonotonic reasoning, pp. 169-181. · Zbl 1258.68031
[34] Kowalski, R; Sergot, M, A logic-based calculus of events, New Generation Computing, 4, 6796, (1986) · Zbl 1356.68221
[35] Kuzelka, O; Zelezny, F, A restarted strategy for efficient subsumption testing, Fundamenta Informaticae, 89, 95-109, (2008) · Zbl 1155.68489
[36] Langley, P. (1995). Learning in humans and machines: Towards an interdisciplinary science, chapter order effects in incremental learning. Amsterdam: Elsevier.
[37] Lavrač, N., & Džeroski, S. (1993). Inductive logic programming: Techniques and applications. London: Routledge.
[38] Li, H-F; Lee, S-Y, Mining frequent itemsets over data streams using efficient window sliding techniques, Expert Systems with Applications, 36, 1466-1477, (2009)
[39] Li, H.-F., Lee, S.-Y., & Shan, M.-K. (2004). An efficient algorithm for mining frequent itemsets over the entire history of data streams. In Proceedings of first international workshop on knowledge discovery in data streams.
[40] List, T., Bins, J., Vazquez, J., & Fisher, R. B. (2005). Performance evaluating the evaluator. In 2nd joint IEEE international workshop on visual surveillance and performance evaluation of tracking and surveillance (pp. 129-136). IEEE.
[41] Lloyd, J. (1987). Foundations of logic programming. Berlin: Springer. · Zbl 0668.68004
[42] Luckham, D. (2001). The power of events: An introduction to complex event processing in distributed enterprise systems. Boston: Addison-Wesley Longman Publishing Co., Inc.
[43] Luckham, D., & Schulte, R. (2008). Event processing glossary, version 1.1. Trento: Event Processing Technical Society.
[44] Maloberti, J; Sebag, M, Fast theta-subsumption with constraint satisfaction algorithms, Machine Learning, 55, 137-174, (2004) · Zbl 1089.68103
[45] Mitchell, T. (1979). Version spaces: An approach to concept learning. PhD thesis, AAI7917262.
[46] Moyle, S. (2003). An investigation into theory completion techniques in inductive logic. PhD thesis, University of Oxford. · Zbl 1017.68545
[47] Mueller, E. (2006). Commonsense reasoning. Burlington: Morgan Kaufmann.
[48] Mueller, ET, Event calculus, Foundations of Artificial Intelligence, 3, 671-708, (2008)
[49] Muggleton, S, Inverse entailment and progol, New Generation Computing, 13, 245-286, (1995)
[50] Muggleton, S., & Bryant, C. (2000). Theory completion using inverse entailment. In International conference on inductive logic programming, pp. 130-146. · Zbl 0994.68623
[51] Muggleton, S; Raedt, L, Inductive logic programming: theory and methods, The Journal of Logic Programming, 19, 629-679, (1994) · Zbl 0816.68043
[52] Muggleton, S; Raedt, L; Poole, D; Bratko, I; Flach, P; Inoue, K; Srinivasan, A, ILP turns 20, Machine Learning, 86, 3-23, (2012) · Zbl 1243.68014
[53] Muggleton, SH; Lin, D; Pahlavi, N; Tamaddoni-Nezhad, A, Meta-interpretive learning: application to grammatical inference, Machine Learning, 94, 25-49, (2014) · Zbl 1319.68121
[54] Otero, RP, Induction of stable models, Inductive Logic Programming, 2157, 193-205, (2001) · Zbl 1007.68506
[55] Otero, RP, Induction of the effects of actions by monotonic methods, Inductive Logic Programming, 2835, 299-310, (2003) · Zbl 1263.68142
[56] Paschke, A. (2005). ECA-RuleML: An approach combining ECA rules with temporal interval-based KR event logics and transactional update logics. Technical report, Technische Universitat Munchen.
[57] Ray, O. (2006). Using abduction for induction of normal logic programs. In ECAI’06 workshop on abduction and induction in articial intelligence and scientic modelling.
[58] Ray, O, Nonmonotonic abductive inductive learning, Journal of Applied Logic, 7, 329-340, (2009) · Zbl 1179.68125
[59] Ray, O., Broda, K., & Russo, A. (2003). Hybrid abductive inductive learning: A generalisation of progol. In Proceedings of the international conference in inductive logic programming (ILP). · Zbl 1263.68144
[60] Richards, B; Mooney, R, Automated refinement of first-order Horn clause domain theories, Machine Learning, 19, 95-131, (1995)
[61] Sakama, C. (2000). Inverse entailment in nonmonotonic logic programs. In Proceedings of the international conference on inductive logic programming (ILP). · Zbl 0994.68112
[62] Sakama, C. (2001). Nonmonotomic inductive logic programming. In Logic programming and nonmotonic reasoning (pp. 62-80). Springer. · Zbl 1010.68031
[63] Sakama, C, Induction from answer sets in nonmonotonic logic programs, ACM Transactions on Computational Logic, 6, 203231, (2005) · Zbl 1367.68039
[64] Santos, J., & Muggleton, S. (2010). Subsumer: A prolog theta-subsumption engine. In Technical communications of the 26th international conference on logic programming. · Zbl 1237.68180
[65] Sloman, M; Lupu, E, Engineering policy-based ubiquitous systems, The Computer Journal, 53, 1113-1127, (2010)
[66] Wrobel, S. (1996). First order theory refinement. In L. De Raedt (Ed.), Advances in inductive logicprogramming (pp. 14-33). Citeseer.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.