Inductive logic programming.

*(English)*Zbl 0712.68022Summary: A new research area, Inductive Logic Programming, is presently emerging. While inheriting various positive characteristics of the parent subjects of Logic Programming and Machine Learning, it is hoped that the new area will overcome many of the limitations of its forebears. The background to present developments within this area is discussed and various goals and aspirations for the increasing body of researchers are identified. Inductive Logic Programming needs to be based on sound principles from both Logic and Statistics. On the side of statistical justification of hypotheses we discuss the possible relationship between Algorithmic Complexity theory and Probably-Approximately-Correct (PAC) Learning. In terms of logic we provide a unifying framework for Muggleton and Buntine’s Inverse Resolution (IR) and Plotkin’s Relative Least General Generalization (RLGG) by rederiving RLGG in terms of IR. This leads to a discussion of the feasibility of extending the RLGG framework to allow for the invention of new predicates, previously discussed only within the context of IR.

##### MSC:

68N17 | Logic programming |

68T05 | Learning and adaptive systems in artificial intelligence |

03B48 | Probability and inductive logic |

##### Keywords:

logic programming; predicate invention; information compression; Learning; Logic Programming; Inverse Resolution##### Software:

GOLEM
PDF
BibTeX
XML
Cite

\textit{S. Muggleton}, New Generation Comput. 8, No. 4, 295--318 (1991; Zbl 0712.68022)

Full Text:
DOI

##### References:

[1] | R.B. Banerji. Learning in the limit in a growing language. InIJCAI-87, pages 280–282, Los Angeles, CA, 1987. Kaufmann. |

[2] | C. Bennett. Logical depth and physical complexity. In R. Herken, editor,The Universal Turing Machine A Half Century Survey, pages 227–257. Kammerer and Unverzagt, Hamburg, 1988. |

[3] | I. Bratko.Prolog for artificial intelligence. Addison-Wesley, London, 1986. · Zbl 0599.68007 |

[4] | W. Buntine. Generalised subsumption and its applications to induction and redundancy.Artificial Intelligence, 36(2):149–176, 1988. · Zbl 0656.68090 · doi:10.1016/0004-3702(88)90001-X |

[5] | R. Carnap.The Continuum of Inductive Methods. Chicago University, Chicago, 1952. · Zbl 0047.37210 |

[6] | G. Chaitin.Information, Randomness and Incompleteness – Papers on Algorithmic Information Theory. World Scientific Press, Singapore, 1987. · Zbl 1013.00525 |

[7] | Dietterich. Limitations of inductive learning. InProceedings of the Sixth International Workshop on Machine Learning, pages 124–128, San Mateo, CA, 1989. Morgan-Kaufmann. |

[8] | A. Ehrenfeucht, D. Haussler, M. Kearns, and L. Valiant. A general lower bound on the number of examples needed for learning. InCOLT 88: Proceedings of the Conference on Learning, pages 110–120, Los Altos, CA, 1988. Morgan-Kaufmann. · Zbl 0679.68158 |

[9] | S. Feferman et al., editor.Gödel’s Collected Works. Oxford University Press, Oxford, 1980. |

[10] | M.S. Fox and J. McDermott. The role of databases in knowledge-based systems. Technical Report CMU-RI-TR-86-3, Carnegie-Mellon University, Robotics Institute, Pittsburgh, PA, 1986. |

[11] | A.M. Frisch and C.D. Page. On inductive generalisation with taxonomic back-ground knowledge. Technical report, University of Illinois, Urbana, 1989. |

[12] | K. Gödel. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter System I.Monats. Math. Phys., 32:173–198, 1931. · JFM 57.0054.02 · doi:10.1007/BF01700692 |

[13] | E.M. Gold. Language identification in the limit.Information and Control, 10:447–474, 1967. · Zbl 0259.68032 · doi:10.1016/S0019-9958(67)91165-5 |

[14] | D. Haussler. Quantifying inductive bias: AI learning algorithms and Valiant’s learning framework.Artificial intelligence, 36:177–221, 1988. · Zbl 0651.68104 · doi:10.1016/0004-3702(88)90002-1 |

[15] | J. Hayes-Michie. News from Brainware.Pragmatica, 1:10–11, 1990. |

[16] | H. Ishizaka. Learning simple deterministic languages. InComputational learning theory: proceedings of the second annual workshop, San Mateo, CA, 1989. Kaufmann. · Zbl 0747.68048 |

[17] | R.A. Kowalski.Logic for Problem Solving. North Holland, 1980. · Zbl 0454.35031 |

[18] | B. Kuipers. Qualitative simulation.Artificial Intelligence, 29:289–338, 1986. · Zbl 0624.68098 · doi:10.1016/0004-3702(86)90073-1 |

[19] | X. Ling and M. Dawes Theory reduction with uncertainty: A reason for theoretical terms. Technical Report 271, University of Western Ontario, 1990. |

[20] | J.W. Lloyd.Foundations of Logic Programming. Springer-Verlag, Berlin, 1984. · Zbl 0547.68005 |

[21] | M.J. Maher. Equivalences of logic programs. InProceedings of Third International Conference on Logic Programming, Berlin, 1986. Springer. · Zbl 0594.68011 |

[22] | T.M. Mitchell, R.M. Keller, and S.T. Kedar-Cabelli. Explanation-based generalization: A unifying view.Machine Learning, 1(1):47–80, 1986. |

[23] | H. Mortimer.The Logic of Induction. Ellis Horwood, Chichester, England, 1988. · Zbl 0683.60001 |

[24] | S.H. Muggleton. Duce, an oracle based approach to constructive induction. InIJCAI-87, pages 287–292. Kaufmann, 1987. |

[25] | S.H. Muggleton. Inverting the resolution principle. InMachine Intellience 12 (in press) Oxford University Press, 1988. |

[26] | S.H. Muggleton. A strategy for constructing new predicates in first order logic. InProceedings of the Third European Working Session on Learning, pages 123–130. Pitman, 1988. |

[27] | S.H. Muggleton.Inductive Acquisition of Expert Knowledge. Addision-Wesley, Wokingham, England, 1990. |

[28] | S.H. Muggleton and W. Buntine. Machine invention of first-order predicates by inverting resolution. InProceedings of the Fifth International Conference on Machine Learning, pages 339–352. Kaufmann, 1988. |

[29] | S.H. Muggleton and C. Feng. Efficient induction of logic programs. InProceedings of the First Conference on Algorithmic Learning Theory, Tokyo, 1990. Ohmsha. |

[30] | T. Niblett. A study of generalisation in logic programs. InEWSL-88, London, 1988. Pitman. |

[31] | G.D. Plotkin.Automatic Methods of Inductive Inference. PhD thesis, Edinburgh University, August 1971. |

[32] | J.R. Quinlan. Discovering rules from large collections of examples: a case study. In D. Michie, editor,Expert Systems in the Micro-electronic Age, pages 168–201. Edinburgh University Press, Edinburgh, 1979. |

[33] | J.R. Quinlan. Learning relations: comparison of a symbolic and a connectionist approach. Technical Report 346, University of Sydney, 1989. |

[34] | J.A. Robinson. A machine-oriented logic based on the resolution principle.JACM, 12(1):23–41, January 1965. · Zbl 0139.12303 · doi:10.1145/321250.321253 |

[35] | C. Rouveirol and J-F Puget. A simple and general solution for inverting resolution. InEWSL-89, pages 201–210, London, 1989. Pitman. |

[36] | C. Sammut and R.B. Banerji. Learning concepts by asking questions. In R. Michalski, J. Carbonnel, and T. Mitchell, editors,Machine Learning: An Artificial Intelligence Approach. Vol. 2, pages 167–192. Kaufmann, Los Altos, CA, 1986. |

[37] | E.Y. Shapiro.Algorithmic program debugging. MIT Press, 1983. · Zbl 0589.68003 |

[38] | E.H. Shortliffe and B. Buchanan. A model of inexact reasoning in medicine.Mathematical Biosciences, 23:351–379, 1975. · doi:10.1016/0025-5564(75)90047-4 |

[39] | S. Slocombe, K. Moore, and M. Zelonf. Engineering expert systems applications. InProceedings of the Annual Conference of the BCS Specialist Group on Expert Systems. British Computer Society, London, 1986. |

[40] | R.J. Solomonoff. A formal theory of inductive inference.J. Comput. Sys., 7:376–388, 1964. · Zbl 0259.68038 |

[41] | L. Sterling and E. Shapiro.The art of Prolog: advanced programming techniques. MIT-Press, Cambridge, MA, 1986. · Zbl 0605.68002 |

[42] | A. Turing. Systems of logic based on ordinals.Proceedings of the London Mathematical Society, pages 161–228, 1939. · Zbl 0021.09704 |

[43] | A. Turing. The automatic computing engine.Lecture to the London Mathematical Society, 1947. |

[44] | R. Wirth. Completing logic programs by inverse resolution. InEWSL-89, pages 239–250, London, 1989, Pitman. |

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.