Higher-order Inductive Declarative Programming
(GR/L21884)
Summary
C. Giraud-Carrier and J.W. Lloyd
Department of Computer Science, University of Bristol, Bristol BS8 1UB, UK
Inductive learning focuses on techniques for (supervised) learning from examples. Traditionally, inductive learners have used the attribute-value language to represent examples. Though the relative simplicity of this attribute-value learning (AVL) representation allows the construction of efficient learning systems, it also restricts their applicability, as examples must be representable by tuples of constants. In some applications, the structure of examples and induced hypotheses is too rich to be captured adequately by an AVL representation. The issue in such cases is not necessarily that the structure cannot be flattened in some reasonable way, but the fact that structural information is essential in inducing good concepts from the examples. Hence, the representation (and subsequently the learning algorithms) must be able to handle complex structures.
The main scientific contribution of our research is the development of a new foundation for inductive learning, based on the use of typed higher-order logic for knowledge representation, that subsumes and naturally extends extant learning frameworks. In particular:
- We have defined a systematic individuals-as-terms approach to knowledge representation for inductive learning and demonstrated the utility of types and higher-order constructs for this purpose.
- We have highlighted the strong link between types and predicates, and used it to show how to construct predicates effectively by composing transformations.
- We have implemented an accuracy-driven decision tree learner and a sequential covering rule induction system, that exploit the notion of composition.
- We have implemented a strongly-typed evolutionary programming system, which includes solutions to depth control and links automatically defined functions with predicate invention.
This work was funded by EPSRC Grant GR/L21884.