Cautious Induction: An Alternative to Clause-at-a Time Hypothesis Construction in Inductive Logic Programming

S Anthony; A M Frisch

doi:10.1007/BF03037581

Cautious Induction: An Alternative to Clause-at-a Time Hypothesis Construction in Inductive Logic Programming

S Anthony, A M Frisch

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

Hypotheses constructed by inductive logic programming (ILP) systems are finite sets of definite clauses. Top-down ILP systems usually adopt the following greedy clause-at-a-time strategy to construct such a hypothesis: start with the empty set of clauses and repeatedly add the clause that most improves the quality of the set.

This paper formulates and analyses an alternative method for constructing hypotheses. The method, called cautious induction, consists of a first stage, which finds a finite set of candidate clauses, and a second stage, which selects a finite subset of these clauses to form a hypothesis. By using a less greedy method in the second stage, cautious induction can find hypotheses of higher quality than can be found with a clause-at-a-time algorithm.

We have implemented a top-down, cautious ILP system called CILS. This paper presents CILS and compares it to Progol, a top-down clause-at-a-time ILP system. The sizes of the search spaces confronted by the two systems are analysed and an experiment examines their performance on a series of mutagenesis learning problems.

Original language	English
Pages (from-to)	25-52
Number of pages	28
Journal	New Generation Computing
Volume	17
Issue number	1
DOIs	https://doi.org/10.1007/BF03037581
Publication status	Published - 1999

Keywords

machine learning
inductive learning
inductive logic programming
cautious induction

Access to Document

10.1007/BF03037581

Cite this

@article{5658b26d533844908c7068755fdd6d46,

title = "Cautious Induction: An Alternative to Clause-at-a Time Hypothesis Construction in Inductive Logic Programming",

abstract = "Hypotheses constructed by inductive logic programming (ILP) systems are finite sets of definite clauses. Top-down ILP systems usually adopt the following greedy clause-at-a-time strategy to construct such a hypothesis: start with the empty set of clauses and repeatedly add the clause that most improves the quality of the set.This paper formulates and analyses an alternative method for constructing hypotheses. The method, called cautious induction, consists of a first stage, which finds a finite set of candidate clauses, and a second stage, which selects a finite subset of these clauses to form a hypothesis. By using a less greedy method in the second stage, cautious induction can find hypotheses of higher quality than can be found with a clause-at-a-time algorithm.We have implemented a top-down, cautious ILP system called CILS. This paper presents CILS and compares it to Progol, a top-down clause-at-a-time ILP system. The sizes of the search spaces confronted by the two systems are analysed and an experiment examines their performance on a series of mutagenesis learning problems.",

keywords = "machine learning, inductive learning, inductive logic programming, cautious induction",

author = "S Anthony and Frisch, {A M}",

year = "1999",

doi = "10.1007/BF03037581",

language = "English",

volume = "17",

pages = "25--52",

journal = "New Generation Computing",

issn = "0288-3635",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - Cautious Induction

T2 - An Alternative to Clause-at-a Time Hypothesis Construction in Inductive Logic Programming

AU - Anthony, S

AU - Frisch, A M

PY - 1999

Y1 - 1999

N2 - Hypotheses constructed by inductive logic programming (ILP) systems are finite sets of definite clauses. Top-down ILP systems usually adopt the following greedy clause-at-a-time strategy to construct such a hypothesis: start with the empty set of clauses and repeatedly add the clause that most improves the quality of the set.This paper formulates and analyses an alternative method for constructing hypotheses. The method, called cautious induction, consists of a first stage, which finds a finite set of candidate clauses, and a second stage, which selects a finite subset of these clauses to form a hypothesis. By using a less greedy method in the second stage, cautious induction can find hypotheses of higher quality than can be found with a clause-at-a-time algorithm.We have implemented a top-down, cautious ILP system called CILS. This paper presents CILS and compares it to Progol, a top-down clause-at-a-time ILP system. The sizes of the search spaces confronted by the two systems are analysed and an experiment examines their performance on a series of mutagenesis learning problems.

AB - Hypotheses constructed by inductive logic programming (ILP) systems are finite sets of definite clauses. Top-down ILP systems usually adopt the following greedy clause-at-a-time strategy to construct such a hypothesis: start with the empty set of clauses and repeatedly add the clause that most improves the quality of the set.This paper formulates and analyses an alternative method for constructing hypotheses. The method, called cautious induction, consists of a first stage, which finds a finite set of candidate clauses, and a second stage, which selects a finite subset of these clauses to form a hypothesis. By using a less greedy method in the second stage, cautious induction can find hypotheses of higher quality than can be found with a clause-at-a-time algorithm.We have implemented a top-down, cautious ILP system called CILS. This paper presents CILS and compares it to Progol, a top-down clause-at-a-time ILP system. The sizes of the search spaces confronted by the two systems are analysed and an experiment examines their performance on a series of mutagenesis learning problems.

KW - machine learning

KW - inductive learning

KW - inductive logic programming

KW - cautious induction

U2 - 10.1007/BF03037581

DO - 10.1007/BF03037581

M3 - Article

SN - 0288-3635

VL - 17

SP - 25

EP - 52

JO - New Generation Computing

JF - New Generation Computing

IS - 1

ER -