×

Nonmonotonic abductive inductive learning. (English) Zbl 1179.68125

Summary: Inductive Logic Programming (ILP) is concerned with the task of generalising sets of positive and negative examples with respect to background knowledge expressed as logic programs. Negation As Failure (NAF) is a key feature of logic programming which provides a means for nonmonotonic commonsense reasoning under incomplete information. But, so far, most ILP research has been aimed at Horn programs which exclude NAF, and has failed to exploit the full potential of normal programs that allow NAF. By contrast, Abductive Logic Programming (ALP), a related task concerned with explaining observations with respect to a prior theory, has been well studied and applied in the context of normal logic programs. This paper shows how ALP can be used to provide a semantics and proof procedure for nonmonotonic ILP that utilises practical methods of language and search bias to reduce the search space. This is done by lifting an existing method called Hybrid Abductive Inductive Learning (HAIL) from Horn clauses to normal logic programs. To demonstrate its potential benefits, the resulting system, called XHAIL, is applied to a process modelling case study involving a nonmonotonic temporal Event Calculus.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68N17 Logic programming

Software:

Aleph
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adé, H.; Denecker, M., AILP: Abductive inductive logic programming, (14th International Joint Conference on Artificial Intelligence (1995), Morgan Kaufmann), 1201-1207
[2] Alrajeh, D.; Ray, O.; Russo, A.; Uchitel, S., Extracting requirements from scenarios with ILP, (16th International Conference on Inductive Logic Programming. 16th International Conference on Inductive Logic Programming, LNCS, vol. 4455 (2007), Springer), 63-77 · Zbl 1201.68081
[3] Apt, K.; Bol, R., Logic programming and negation: A survey, Journal of Logic Programming, 19-20, 9-71 (1994) · Zbl 0942.68518
[4] Bain, M.; Muggleton, S., Non-monotonic learning, (Machine Intelligence 12 (1991), OUP), 105-119
[5] Bergadano, F.; Gunetti, D.; Nicosia, M.; Ruffo, G., Learning logic programs with negation as failure, (De Raedt, L., Advances in Inductive Logic Programming (1996), IOS Press), 107-123
[6] Clark, K., Negation as failure rule, (Gallaire, H.; Minker, J., Logic and Databases (1978), Plenum Press), 293-322
[7] Dimopoulos, Y.; Kakas, A., Learning non-monotonic logic programs: Learning exceptions, (8th European Conference on Machine Learning. 8th European Conference on Machine Learning, LNAI, vol. 912 (1995), Springer), 122-138
[8] Eshghi, K.; Kowalski, R., Abduction compared with negation by failure, (6th International Conference on Logic Programming (1989), MIT Press), 234-254
[9] Esposito, F.; Fanizzi, N.; Ferilli, S.; Basile, T.; Di Mauro, N., Multistrategy operators for relational learning and their cooperation, Fundamenta Informaticae, 69, 4, 389-409 (2006) · Zbl 1096.68130
[10] Esposito, F.; Ferilli, S.; Basile, T.; Di Mauro, N., Inference of abduction theories for handling incompleteness in first-order learning, Knowledge and Information Systems, 11, 2, 217-242 (2007)
[11] F. Esposito, A. Laterza, D. Malerba, G. Semeraro, Refinement of Datalog programs, in: Proceedings of the MLnet Familiarization Workshop on Data Mining with Inductive Logic Programming, 1996, pp. 73-94; F. Esposito, A. Laterza, D. Malerba, G. Semeraro, Refinement of Datalog programs, in: Proceedings of the MLnet Familiarization Workshop on Data Mining with Inductive Logic Programming, 1996, pp. 73-94
[12] Esposito, F.; Semeraro, G.; Fanizzi, N.; Ferilli, S., Multistrategy theory revision: Induction and abduction in INTHELEX, Machine Learning, 38, 1/2, 133-156 (2000) · Zbl 0960.68603
[13] Fogel, L.; Zaverucha, G., Normal programs and multiple predicate learning, (8th International Workshop on Inductive Logic Programming (1998), Springer), 175-184
[14] Furukawa, K., On the completion of the most specific hypothesis computation in inverse entailment for mutual recursion, (1st International Conference on Discovery Science. 1st International Conference on Discovery Science, LNCS, vol. 1532 (1998), Springer), 315-325
[15] Gelfond, M.; Lifschitz, V., The stable model semantics for logic programming, (5th International Conference on Logic Programming (1988), MIT Press), 1070-1080
[16] Gelfond, M.; Lifschitz, V., Classical negation in logic programs and disjunctive databases, New Generation Computing, 9, 3/4, 365-386 (1991) · Zbl 0735.68012
[17] Hirata, K., Flattening and implication, (10th International Conference on Algorithmic Learning Theory. 10th International Conference on Algorithmic Learning Theory, LNAI, vol. 1720 (1999), Springer), 157-168 · Zbl 0949.68042
[18] Inoue, K., Induction as consequence finding, Machine Learning, 55, 2, 109-135 (2004) · Zbl 1101.68078
[19] Inoue, K.; Kudoh, Y., Learning extended logic programs, (15th International Joint Conference on Artificial Intelligence, vol. I (1997), Morgan Kaufmann), 176-181
[20] Jacob, F.; Monod, J., Genetic regulatory mechanisms in the synthesis of proteins, Journal of Molecular Biology, 3, 318-356 (1961)
[21] Kakas, A.; Kowalski, R.; Toni, F., Abductive logic programming, Journal of Logic and Computation, 2, 6, 719-770 (1992) · Zbl 0778.68081
[22] Kakas, A.; Mancarella, P., Generalized stable models: A semantics for abduction, (9th European Conference on Artificial Intelligence (1990), Pitman), 385-391
[23] Kakas, A.; Riguzzi, F., Abductive concept learning, New Generation Computing, 18, 3, 243-294 (2000)
[24] Kowalski, R.; Sergot, M., A logic-based calculus of events, New Generation Computing, 4, 67-95 (1986) · Zbl 1356.68221
[25] Lamma, E.; Riguzzi, F.; Pereira, L., Strategies in combined learning via logic programs, Machine Learning, 38, 1-2, 63-87 (2000) · Zbl 0960.68024
[26] Lifschitz, V., Action languages, answer sets and planning, (Apt, K.; Marek, V.; Truszczynski, M.; Warren, D., The Logic Programming Paradigm: A 25 Year Perspective (1999), Springer), 357-373 · Zbl 0979.68517
[27] Lloyd, J., Foundations of Logic Programming (1987), Springer · Zbl 0668.68004
[28] Martin, L.; Vrain, C., A three-valued framework for the induction of general logic programs, (De Raedt, L., Advances in Inductive Logic Programming (1996), IOS Press), 219-235
[29] McCarthy, J.; Hayes, P., Some philosophical problems from the standpoint of artificial intelligence, Machine Intelligence, 4, 463-502 (1969) · Zbl 0226.68044
[30] Miller, R.; Shanahan, M., Some alternative formulations of the event calculus, (Kakas, A.; Sadri, F., Computational Logic: Logic Programming and Beyond, Essays in Honour of Robert A. Kowalski, Part II (2002), Springer-Verlag), 452-490 · Zbl 1012.68192
[31] Moyle, S., Using theory completion to learn a robot navigation control program, (12th International Workshop on Inductive Logic Programming. 12th International Workshop on Inductive Logic Programming, LNAI, vol. 2583 (2002), Springer), 182-197 · Zbl 1017.68545
[32] S. Moyle, An investigation into theory completion techniques in Inductive Logic Programming, PhD thesis, University of Oxford, UK, 2003; S. Moyle, An investigation into theory completion techniques in Inductive Logic Programming, PhD thesis, University of Oxford, UK, 2003 · Zbl 1017.68545
[33] Moyle, S.; Muggleton, S., Learning programs in the event calculus, (7th International Workshop on Inductive Logic Programming. 7th International Workshop on Inductive Logic Programming, LNAI, vol. 1297 (1997), Springer), 205-212
[34] Mueller, E., Event calculus reasoning through satisfiability, Journal of Logic and Computation, 14, 5, 703-730 (2004) · Zbl 1062.68118
[35] Mueller, E., Commonsense Reasoning (2006), Morgan Kaufmann
[36] Muggleton, S., Inverse entailment and Progol, New Generation Computing, 13, 3-4, 245-286 (1995)
[37] Muggleton, S.; Bryant, C., Theory completion using inverse entailment, (10th International Conference on Inductive Logic Programming. 10th International Conference on Inductive Logic Programming, LNCS, vol. 1866 (2000), Springer), 130-146 · Zbl 0994.68623
[38] Muggleton, S.; De Raedt, L., Inductive logic programming: Theory and methods, Journal of Logic Programming, 19-20, 629-679 (1994) · Zbl 0816.68043
[39] Nicolas, P.; Duval, B., Representation of incomplete knowledge by induction of default theories, (6th International Conference on Logic Programming and Nonmonotonic Reasoning. 6th International Conference on Logic Programming and Nonmonotonic Reasoning, LNAI, vol. 2173 (2001), Springer), 160-172 · Zbl 1007.68176
[40] Otero, R., Induction of stable models, (11th International Conference on Inductive Logic Programming. 11th International Conference on Inductive Logic Programming, LNAI, vol. 2157 (2001), Springer), 193-205 · Zbl 1007.68506
[41] Otero, R., Induction of the effects of actions by monotonic methods, (13th International Conference on Inductive Logic Programming. 13th International Conference on Inductive Logic Programming, LNCS, vol. 2835 (2003), Springer), 299-310 · Zbl 1263.68142
[42] Otero, R., Induction of the indirect effects of actions by monotonic methods, (15th International Conference on Inductive Logic Programming. 15th International Conference on Inductive Logic Programming, LNCS, vol. 3625 (2005), Springer), 279-294 · Zbl 1134.68478
[43] De Raedt, L., Interactive Theory Revision: An Inductive Logic Programming Approach. Knowledge-based Systems (1992), Academic Press
[44] O. Ray, Hybrid abductive-inductive learning, PhD thesis, Department of Computing, Imperial College London, UK, 2005; O. Ray, Hybrid abductive-inductive learning, PhD thesis, Department of Computing, Imperial College London, UK, 2005
[45] O. Ray, Using abduction for induction of normal logic programs, in: ECAI’06 Workshop on Abduction and Induction in Artificial Intelligence and Scientific Modelling, 2006, pp. 28-31; O. Ray, Using abduction for induction of normal logic programs, in: ECAI’06 Workshop on Abduction and Induction in Artificial Intelligence and Scientific Modelling, 2006, pp. 28-31
[46] O. Ray, Inferring process models from temporal data using abduction and induction, in: 1st International Workshop on the Induction of Process Models, 2007; O. Ray, Inferring process models from temporal data using abduction and induction, in: 1st International Workshop on the Induction of Process Models, 2007
[47] Rouveirol, C., Flattening and saturation: Two representation changes for generalization, Machine Learning, 14, 1, 219-232 (1994) · Zbl 0804.68024
[48] Sakama, C., Some properties of inverse resolution in normal logic programs, (9th International Workshop on Inductive Logic Programming. 9th International Workshop on Inductive Logic Programming, LNCS, vol. 1634 (1999), Springer), 279-290
[49] Sakama, C., Induction from answer sets in nonmonotonic logic programs, ACM Transactions on Computational Logic, 6, 2, 203-231 (2005) · Zbl 1367.68039
[50] J. Seitzer, Stable ILP: exploring the added expressivity of negation in the background knowledge, in: IJCAI’95 Workshop on Frontiers of Inductive Logic Programming, 1997; J. Seitzer, Stable ILP: exploring the added expressivity of negation in the background knowledge, in: IJCAI’95 Workshop on Frontiers of Inductive Logic Programming, 1997
[51] Semeraro, G.; Esposito, F.; Malerba, D.; Fanizzi, N.; Ferilli, S., A logic framework for the incremental inductive synthesis of datalog theories, (7th International Workshop on Logic Programming Synthesis and Transformation. 7th International Workshop on Logic Programming Synthesis and Transformation, LNCS, vol. 1463 (1997), Springer), 300-321
[52] Shanahan, M., Solving the Frame Problem: A Mathematical Investigation of the Common Sense Law of Inertia (1997), MIT Press
[53] Srinivasan, A., The Aleph Manual (version 4) (2003), Machine Learning Group: Machine Learning Group Oxford University Computing Lab
[54] Tamaddoni-Nezhad, A.; Chaleil, R.; Kakas, A.; Sternberg, M.; Nicholson, J.; Muggleton, S., Modeling the effects of toxins in metabolic networks, Engineering in Medicine and Biology Magazine, 26, 2, 209-230 (2007)
[55] Taylor, K., Inverse resolution of normal clauses, (3rd International Workshop on Inductive Logic Programming (1993), Joseph Stefan Institute), 165-178
[56] Yamamoto, A., Which hypotheses can be found with Inverse Entailment, (7th International Workshop on Inductive Logic Programming. 7th International Workshop on Inductive Logic Programming, LNAI, vol. 1297 (1997), Springer), 296-308
[57] Yamamoto, A., Using abduction for induction based on bottom generalisation, (Flach, P.; Kakas, A., Abduction and Induction: Essays on their Relation and Integration. Abduction and Induction: Essays on their Relation and Integration, Applied Logic Series, vol. 18 (2000), Kluwer), 267-280 · Zbl 1032.68762
[58] Yamamoto, A., Hypothesis finding based on upward refinement of residue hypotheses, Theoretical Computer Science, 298, 5-19 (2003) · Zbl 1038.68022
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.