[ Bristol CS | Index | ML group | Peter Flach | Papers | Presentations | PhD thesis ] Although induction is a fruitful and widely used form of reasoning, there is a problem: we don't know how it works. How many crows should one observe in order to conclude that all crows are black? After all, not all swans are white, and the same hand that feeds the hen day after day ultimately wrings her neck. The justification of inductive conclusions is a notorious philosophical problem, and every inductively inferred rule is, at its best, a plausible conjecture, for which however every next example may turn out to be a counterexample (as the hen discovered to her disgrace).
There is, however, another problem: a general theory as to which inductive conjectures are refuted by the observed instances, and which are still possible, does not exist. What is the logic of conjectures? This problem of `conjectural reasoning' forms the subject of my thesis. Starting from earlier work in philosophy, computer science and logic, I have tried to reduce the problem to manageable proportions, and to suggest the beginnings of a solution.
The principal result of this attempt is twofold. First of all, I claim that the logic of induction is not essentially different from, for example, deductive logic, as long as we are prepared to broaden the usual conception of logic somewhat. This frees the way for the application of a recently developed description method -- put forward to aid the analysis of reasoning with general rules and exceptions -- to inductive reasoning. The second result of my thesis is a distinction between and logical characterisation of two different forms of induction: explanatory induction, which aims at explaining observed cases, and confirmatory induction, where the inductive conjectures are confirmed by the observations, however without explaining the latter. I show that this distinction can be traced back to philosophical work of half a century and a century ago, respectively, making furthermore use of recent work in the field of artificial intelligence.
What follows is a brief overview of the different chapters.
After an introductory chapter I discuss in chapter 2 the philosophical backgrounds of induction, thereby restricting attention to the work of Peirce on abduction or explanatory reasoning, and Hempel's logical analysis of the notion of `confirmation' in statements like `this hypothesis is confirmed by that evidence'. As Hempel noticed, the unconcerned combination of intuitions about `explanation' and `confirmation' leads to paradoxes; the solution I propose is simply not to combine, but rather to discern between them. Carnap's `inductive logic' is also discussed sideways; it does not, however, play a significant role in the rest of the thesis, since Carnap was not so much concerned with the nature of inductive arguments, but rather with the question how plausible an arbitrary hypothesis is, given the observed facts.
Chapter 3 deals with practical induction methods as applied in the field of artificial intelligence. I demonstrate that the distinction between explanatory and confirmed hypotheses occurs here also: the usual classification rules are explanatory hypotheses, while integrity constraints, which can be found, for example, in databases, are confirmed by the data without being powerful enough to explain them. In chapter 4 I discuss the method, initiated by Gabbay and further developed by Kraus, Lehmann and Magidor, for analysing plausible reasoning. According to this method, a form of reasoning is abstracted into a so-called consequence relation. Since this method makes little presuppositions about the nature of the reasoning form in question, it is equally suitable for analysing other forms of reasoning such as induction: it is in fact a methodology.
The next three chapters form the core of the thesis. In chapter 5 I investigate whether it is at all possible to speak of a logic of induction, what components such a logic is built of, and its scope and limits. The key result of this analysis is a generalisation of the truth-preserving semantics of deductive logic into an abstract preservation semantics. The semantic objects that are to be preserved depend on the reasoning form at hand. In this respect one can think of `explanatory power' in the case of explanatory induction, and `regularity' of interpretations in the case of confirmatory induction; this is further elaborated in chapter 7.
The following two chapters contain a logical analysis of conjectural consequence relations, in the spirit of the work of Kraus et al. Chapter 6 presents an overview of possible structural properties of conjectural consequence relations, and in chapter 7 three distinct systems of such rules are proposed and semantically characterised. Furthermore, in this chapter a preliminary partial semantics for confirmatory induction is given.
Finally, the theory developed in the previous chapters is applied in chapter 8 to the problem of inducing integrity constraints in databases, aimed at making explicit the structure that is implicitly present in the data. The constraints thus discovered can be used, with some help of the user, to re-organise the data in a more meaningful and less redundant way.