Logic for Learning

`Logic for Learning' is available from Springer.

Alkemy

Amongst other things, the book provides the theoretical foundations for Alkemy, a decision-tree learning system designed and implemented by Kee Siong Ng that is able to learn comprehensible theories from structured data. Alkemy is available for downloading here.

Preface

This book is concerned with the rich and fruitful interplay between the fields of computational logic and machine learning. The intended audience is senior undergraduates, graduate students, and researchers in either of those fields. For those in computational logic, no previous knowledge of machine learning is assumed and, for those in machine learning, no previous knowledge of computational logic is assumed.

The logic used throughout the book is a higher-order one. Higher-order logic is already heavily used in some parts of computer science, for example, theoretical computer science, functional programming, and hardware verification, mainly because of its great expressive power. Similar motivations apply here as well: higher-order functions can have other functions as arguments and this capability can be exploited to provide abstractions for knowledge representation, methods for constructing predicates, and a foundation for logic-based computation.

The book should be of interest to researchers in machine learning, especially those who study learning methods for structured data. Machine learning applications are becoming increasingly concerned with applications for which the individuals that are the subject of learning have complex structure. Typical applications include text learning for the World Wide Web and bioinformatics. Traditional methods for such applications usually involve the extraction of features to reduce the problem to one of attribute-value learning. The book investigates alternative approaches that involve learning directly from an accurate representation of the complex individuals and provides a suitable knowledge representation formalism and generalised learning algorithms for this purpose. Throughout, great emphasis is placed on learning comprehensible theories. There is no attempt at a comprehensive account of machine learning; instead the book concentrates largely on the problem of learning from structured data. For those readers primarily interested in the applications to machine learning, a `shortest path' through the preceding chapters to get to this material is indicated in Chap. 1.

The book serves as an introduction for computational logicians to machine learning, a particularly interesting and important application area of logic, and also provides a foundation for functional logic programming languages. However, it does not provide a comprehensive account of higher-order logic, much less computational logic, concentrating instead on those aspects of higher-order logic that can be applied to learning.

There is also something new here for researchers in knowledge representation. The requirement of a suitable formalism for representing individuals in machine-learning applications has led to the development of a novel class of higher-order terms for representing such individuals. The theoretical foundations of this class of terms are developed in detail. While the main application here is to machine learning, this class has applications throughout computer science wherever logic is used as a knowledge representation formalism.

There is a Web site for the book that can be found at
http://discus.anu.edu.au/~jwl/LogicforLearning/
The Alkemy learning system described in the book can be obtained from there.

I am greatly indebted to my collaborators Antony Bowers, Peter Flach, Thomas Gaertner, Christophe Giraud-Carrier, and Kee Siong Ng over the last six years. Without their contributions, this book would have not been possible. Kee Siong Ng implemented Alkemy and contributed greatly to its design. I thank Hendrik Blockeel, Luc De Raedt, Michael Hanus, Stefan Kramer, Nada Lavrac, Stephen Muggleton, David Page, Ross Quinlan, Claude Sammut, Joerg Siekmann, and Ashwin Srinivasan for technical advice on various aspects of the material. Finally, this book builds upon a long tradition of logical methods in machine learning. In this respect, I would like to acknowledge the works of Gordon Plotkin, Ryszard Michalski, Ehud Shapiro, Ross Quinlan, Stephen Muggleton, and Luc De Raedt that have been particularly influential.

Contents

1. Introduction

1.1 Outline of the Book
1.2 Setting the Scene
1.3 Introduction to Learning
1.4 Introduction to Logic
Bibliographical Notes
Exercises

2. Logic

2.1 Types
2.2 Type Substitutions
2.3 Terms
2.4 Subterms
2.5 Term Substitutions
2.6 lambda-Conversion
2.7 Model Theory
2.8 Proof Theory
Bibliographical Notes
Exercises

3. Individuals

3.1 Default Terms
3.2 Normal Terms
3.3 An Equivalence Relation on Normal Terms
3.4 A Total Order on Normal Terms
3.5 Basic Terms
3.6 Metrics on Basic Terms
3.7 Kernels on Basic Terms
Bibliographical Notes
Exercises

4. Predicates

4.1 Transformations
4.2 Standard Predicates
4.3 Regular Predicates
4.4 Predicate Rewrite Systems
4.5 The Implication Preorder
4.6 Efficient Construction of Predicates
Bibliographical Notes
Exercises

5. Computation

5.1 Programs as Equational Theories
5.2 Definitions of Some Basic Functions
5.3 Programming with Abstractions
Bibliographical Notes
Exercises

6. Learning

6.1 Decision-Tree Learning
6.2 Illustrations
Bibliographical Notes
Exercises

A. Appendix

A.1 Well-Founded Sets

References

Notation

Index

Return to home page