Theory-Generating Abduction from Finite Good Examples

The theory-generating abduction is a kind of abduction which generates a theory to explain a surprising fact, and proposes it as a hypothesis. In this paper, by regarding the surprising facts as good examples for machine learning, we investigate theory-generating abduction from good examples. First, we introduce a subclass of logic programs, called weakly reducing programs $ WR_{d} with dotted pairs. For the class $ WR_{d} $, we formulate the concept of good examples, and design the algorithm of theory-generating abduction. Then, we show that the program of the class $ WR_{d} $ is constructed correctly by this algorithm from finite good examples. Furthermore, by using not only dotted pairs but also concatenations, we extend the class to weakly reducing programs $ WR_{d,c} $ with dotted pairs and concatenations. From the viewpoint of learning logic programs, any good example for the program of the class $ WR_{d,c} $ should be given by using only dotted pairs. Then, it is a problem how to determine which of the arguments\u27 terms for any good example are described by concatenations. In this paper, we design the algorithm of theory-generating abduction for the class $ WR_{d} $, which determines such arguments, from good examples described by dotted pairs. We show that the program of the class $ WR_{d,c} is also constructed correctly by this algorithm from finite good examples described by dotted pairs