Abstract
This paper presents a logic framework for the incremental inductive synthesis of Datalog theories. It allows us to cast the problem as a process of abstract diagnosis and debugging of an incorrect theory. This process involves a search in a space, whose algebraic structure (conferred by the notion of object identity) makes easy the definition of algorithms that meet several properties which are deemed as desirable from the point of view of the theoretical computer science. Such algorithms embody two ideal refinement operators, one for generalizing incomplete clauses, and the other one for specializing inconsistent clauses.
These algorithms have been implemented in INCR/H, an incremental learning system whose main characteristic consists of the capability of extending autonomously the search to the space of Datalog¬ clauses, when no correct theories exist in the space of Datalog clauses. Experimental results show that INCR/H is able to cope effectively and efficiently with the real-world task of document understanding.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ceri, S., Gottlob, G., and Tanca, L.: Logic Programming and Databases. Springer-Verlag, Berlin Heidelberg New York (1990)
Esposito, F., Malerba, D., and Semeraro, G.: Automated Acquisition of Rules for Document Understanding. Proceedings of the 2nd International Conference on Document Analysis and Recognition ICDAR93. IEEE Computer Society Press, Los Alamitos, CA (1993) 650–654
Esposito, F., Malerba, D., and Semeraro, G.: Multistrategy Learning for Document Recognition. Applied Artificial Intelligence: An Int. J. 8 (1994) 33–84
Esposito, F., Malerba, D., Semeraro, G., Brunk, C., and Pazzani, M.: Traps and Pitfalls when Learning Logical Definitions from Relations. In: Ras, Z.W., Zemankova, M. (eds.): Methodologies for Intelligent Systems. Lecture Notes in Artificial Intelligence, Vol. 869. Springer-Verlag, Berlin Heidelberg New York (1994) 376–385
Esposito, F., Laterza, A., Malerba, D., and Semeraro, G.: Locally Finite, Proper and Complete Operators for Refining Datalog Programs. In: Ras, Z.W., Michalewicz, M. (eds.): Foundations of Intelligent Systems. Lecture Notes in Artificial Intelligence, Vol. 1079. Springer-Verlag, Berlin Heidelberg New York (1996) 468–478
Hayes-Roth, F., and McDermott, J.: Knowledge acquisition from structural descriptions. Proceed. of the 5th International Joint Conference on AI. Cambridge, MA (1977) 356–362
Helft, N.: Inductive Generalization: A Logical Framework. In: Bratko, I., Lavrac, N. (eds.): Progress in Machine Learning. Sigma Press, Wilmslow (1987) 149–157
Jaffar, J., and Maher, M.J.: Constraint Logic Programming: a Survey. J. Logic Programming 19 (1994) 503–581
Kanellakis, P.C.: Elements of Relational Database Theory. In: Van Leeuwen, J. (ed.): Handbook of Theoretical Computer Science, Volume B, Formal Models and Semantics. Elsevier Science Publishers (1990) 1073–1156
Komorowski, J., and Trcek, S.: Towards Refinement of Definite Logic Programs. In: Ras, Z.W., Zemankova, M. (eds.): Methodologies for Intelligent Systems. Lecture Notes in Artificial Intelligence, Vol. 869. Springer-Verlag, Berlin Heidelberg New York (1994) 315–325
Lloyd, J.W.: Foundations of Logic Programming. 2nd edn. Springer-Verlag, Berlin Heidelberg New York (1987)
Orkin, M., and Drogin, R.: Vital Statistics. McGraw-Hill, New York (1990)
Plotkin, G.D.: A Note on Inductive Generalization. In: Meltzer, B., Michie, D. (eds.): Machine Intelligence 5. Edinburgh University Press (1970) 153–163
Plotkin, G.D.: Building-in Equational Theories. In: Meltzer, B., Michie, D. (eds.): Machine Intelligence 7. Edinburgh University Press (1972) 73–90
Reiter, R.: Equality and domain closure in first order databases. J. ACM 27 (1980) 235–249
Semeraro, G., Esposito, F., Malerba, D., Brunk, C., and Pazzani, M.: Avoiding Non-Termination when Learning Logic Programs: A Case Study with FOIL and FOCL. In: Fribourg, L., Turini, F. (eds.): Logic Program Synthesis and Transformation-Meta-Programming in Logic. Lecture Notes in Computer Science, Vol. 883. Springer-Verlag, Berlin Heidelberg New York (1994) 183–198
Semeraro, G., Esposito, F., Fanizzi, N., and Malerba, D.: Revision of Logical Theories. In: Gori, M., Soda, G. (eds.): Topics in Artificial Intelligence. Lecture Notes in Artificial Intelligence, Vol. 992. Springer-Verlag, Berlin Heidelberg New York (1995) 365–376
Semeraro, G., Esposito, F., and Malerba, D.: Ideal Refinement of Datalog Programs. In: Proietti, M. (ed.): Logic Program Synthesis and Transformation. Lecture Notes in Computer Science, Vol. 1048. Springer-Verlag, Berlin Heidelberg New York (1996) 120–136
Semeraro, G., Esposito, F., Malerba, D., Fanizzi, N., and Ferilli, S.: Machine Learning + On-line Libraries = IDL. In: Peters, C., Thanos, C. (eds.): Research and Advanced Technology for Digital Libraries. Lecture Notes in Computer Science, Vol. 1324. Springer-Verlag, Berlin Heidelberg New York (1997) 195–214
van der Laag, P.R.J., and Nienhuys-Cheng, S.-H.: A Note on Ideal Refinement Operators in Inductive Logic Programming. In: Wrobel, S. (ed.): Proceedings of the Fourth International Workshop on Inductive Logic Programming ILP-94. GMD-Studien Nr. 237 (1994) 247–260
van der Laag, P.R.J., and Nienhuys-Cheng, S.-H.: Existence and Nonexistence of Complete Refinement Operators. In: Bergadano, F., De Raedt, L. (eds.): Machine Learning: ECML-94-Proceedings of the European Conference on Machine Learning. Lecture Notes in Artificial Intelligence, Vol. 784. Springer-Verlag, Berlin Heidelberg New York (1994) 307–322
van der Laag, P.R.J.: An Analysis of Refinement Operators in Inductive Logic Programming. Ph.D. dissertation, Tinbergen Institute Research Series (1995)
VanLehn, K.: Efficient Specialization of Relational Concepts. Machine Learning 4 (1989) 99–106
Wrobel, S.: On the proper definition of minimality in specialization and theory revision. In: Brazdil, P.B. (ed.): Machine Learning: ECML-93-Proceedings of the European Conference on Machine Learning. Lecture Notes in Artificial Intelligence, Vol. 667. Springer-Verlag, Berlin Heidelberg New York (1993) 65–82
Wrobel, S.: Concept Formation and Knowledge Revision. Kluwer Academic Publishers, Dordrecht Boston London (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Semeraro, G., Esposito, F., Malerba, D., Fanizzi, N., Ferilli, S. (1998). A Logic Framework for the Incremental Inductive Synthesis of Datalog Theories. In: Fuchs, N.E. (eds) Logic Program Synthesis and Transformation. LOPSTR 1997. Lecture Notes in Computer Science, vol 1463. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49674-2_16
Download citation
DOI: https://doi.org/10.1007/3-540-49674-2_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65074-4
Online ISBN: 978-3-540-49674-8
eBook Packages: Springer Book Archive