Logo[ Bristol CS | Index | ML group | Peter Flach | Papers | Presentations | PhD thesis ]

Introduction and overview

-- in which the motivation for this study will be given, its scope will be delineated, preliminary concepts and notation will be defined, and an overview will be provided of what is still to come --



THIS THESIS GIVES an account of my investigations into the logical foundations of inductive reasoning. Roughly speaking, induction consists in identifying the similarities between observed objects or events, and hypothetically extending those similarities to unobserved objects or future events. It constitutes a mode of reasoning which plays a role in the acquisition of scientific theories, as well as the acquisition of the descriptive vocabulary needed to reason about the objects and events encountered in everyday life, although, it must be added, philosophers (and psychologists) disagree about the importance of induction in these processes. In recent years researchers in artificial intelligence have explored the realisation of inductive procedures by means of computer programs, not only with the purpose to automate the formation of scientific theories and concept taxonomies, but also aiming at extending inductive techniques to new tasks, such as the construction of computer programs from examples of their intended behaviour (like in inductive logic programming). The initial motivation for the present study grew out of a perceived need for a formal framework in which the various inductive techniques that are used in practice can be precisely characterised and related to each other. As such, it should be viewed as a methodological investigation into the formal aspects of inductive methods as used in computer science in general, and artificial intelligence in particular.

The field of artificial intelligence seeks to implement aspects of human cognitive behaviour by means of computer programs. By its very nature, the field has a strong inclination towards epistemological subjects, as they were traditionally studied by philosophers and logicians[1]. Clearly, researchers in each of these fields study the same subjects with quite different aims. For instance, philosophers are interested in such issues as the scope and justification of human knowledge; logicians are interested in formalising reasoning processes; and computer scientists may use techniques similar to human reasoning methods to solve particular problems. Despite these different aims, methods and results from one of these fields may be relevant for the others. For instance, Gödel's proof of the incompleteness of first-order predicate logic as soon as it includes fundamental number theory has some serious philosophical implications; and the computer scientist's pursuit for an efficiently implementable deduction strategy has spawned an innumerable amount of logical investigations. Many problems in artificial intelligence would therefore benefit from an approach that is not completely ignorant of related views, and inductive reasoning is no exception in this respect. In this thesis inductive reasoning is studied in a multidisciplinary context, combining perspectives from philosophy, logic, and artificial intelligence.


Philosophical investigations of inductive reasoning have concentrated on the justification of inductively acquired knowledge: the infamous `Problem of Induction'. Not only is this a very complex problem, philosophers disagree about what exactly should be understood as a justification. Many scholars tend to believe that this requires, in some form or another, an assessment of the truth of the inductive conclusion, given the truth of the premises. Other philosophers claim that describing the inferential patterns underlying induction suffices. For instance, Nelson Goodman states that `the basic task in justifying an inductive inference is to show that it conforms to the general rules of induction' (Goodman, 1954, p.374). Such rules of induction delimit what kind of argument we are prepared to accept as inductive argument -- they cannot have, and do not need, any further justification than their compliance with common practice. Furthermore, as Goodman notes, this renders the inductive justification problem completely analogous to the justification of deduction: there, also, a deductive argument is valid if it is in accordance with the rules of the game -- rules that come very close to formalising our intuitions about deduction, it is true, but which nevertheless can also only be justified by an appeal to intuition.

It would be, I believe, a mistake to think that the `Problem of Induction' can be completely reduced to the problem of devising a proper set, or proper sets, of rules of induction, because a solution to the latter problem leaves unanswered the question how to assess the truth of the inductive conclusion. The two problems -- justifying inductive reasoning and describing inductive reasoning -- are, in the view developed in this thesis, relatively unrelated. Furthermore, I think that the justification problem is not reserved for induction, but manifests itself in any form of non-deductive reasoning. In this thesis I will concentrate on the description problem rather than the justification problem, although I will also spend some words on the latter.


As a separate branch of science, logic has emerged only relatively recently. Until the twentieth century questions regarding the patterns underlying human reasoning were considered to belong to philosophy. This century has seen a tremendous breakthrough in the formalisation of mathematical reasoning, and as a result logical investigations have become more technical and less philosophical. Logic, as we know it today, is a technical discipline with the mathematics of deductive logic as its main subject.

Withouth questioning the worth of current-day logical investigations, I consider it regrettable that the original, general question regarding the patterns underlying human reasoning has been overpowered by a rather more specific question concerning the logical patterns of deductive reasoning. It is true that non-deductive forms of reasoning can never be formalised to the same extent as deductive reasoning, for the simple reason that the latter has a built-in notion of `correct' reasoning which the former lack. However, I believe that some present-day logical tools can be successfully used to obtain a deeper understanding of non-deductive forms of reasoning, and this thesis is meant as a contribution in this direction.

Artificial intelligence

If logic is a young field, artificial intelligence is still in its infancy. Artificial intelligence can be described as the field that aims to automate human cognitive abilities, in order to improve the usefulness of computers[2]. Artificial intelligence research sheds a new light on many old philosophical problems by taking a computational viewpoint. For instance, many philosophers, including Peirce and Popper, think that scientific hypotheses come to us in a `flash of insight', and not by an algorithmic process consisting of small reasoning steps. There is however, as Peirce noted, a certain relation between the hypothesis and the observations preceding it, parts of which can be logically formalised, and such a formal relation can be computed[3]. While the tendency in philosphy has been `humans do not do this algorithmically, so don't bother about the logical relation', the artificial intelligence attitude is `but I want my computer to do it algorithmically, so I need the exact logical relation as a specification for the computer program'.

We could say that artificial intelligence researchers are philosophical programmers (or that philosophers are artificial intelligence designers). The interplay between the two disciplines is likely to produce new insights, and this thesis is hoped to contribute in that respect.


In this section I will introduce the most important concepts, notation and terminology used throughout the thesis. A summary of many of these terms can be found in an appendix.


If it were possible, at this stage, to give a precise, coherent and undisputed definition of the terms used in the following chapters, this thesis wouldn't have been written. For instance, there is no well-established definition of induction, and the interpretation of the term `abduction' is a battlefield. The following discussion of the terminology I use in this thesis is therefore partly premature and subjective.

Reasoning is an informal term denoting the process of forming arguments, i.e. drawing conclusions from premises, and logic is the formal study of that process. It is taken for granted that different reasoning forms can be identified, such as inductive reasoning, deductive reasoning, plausible reasoning, and so forth; again, this term will be used informally. The formalisation of different reasoning forms and their relations is seen as the main goal of logic, resulting in a catalogue of reasoning forms; such a catalogue, or a coherent part of it, will be referred to as a descriptive logical theory[4].

My definition of the deductive reasoning form is rather generous. An argument is deductive if the conclusion cannot be contradicted by new knowledge without contradicting the premises also; a form of reasoning is deductive if it only allows deductive arguments. Another way to say the same thing is: deduction is the logic of non-defeasible reasoning. This is not meant to say that there is a single deductive logic, and that it is clear which arguments are deductively valid and which are not. On the contrary: the argument `two plus two equals four; therefore, if the moon is made of green cheese, then two plus two equals four' will be rejected by those who favour a causal or relevance interpretation of if-then rather than a truth-functional interpretation. However, as soon as such an argument is accepted as deductively valid, the only way to defeat the conclusion is by denying that two plus two equals four, and this defeats the premises also. Note that I didn't talk about the logical language, or about the proposed semantics: modal, temporal, relevance, and intuitionistic logics are all formalisations, sometimes conflicting, of certain aspects of deductive reasoning.

Non-deductive reasoning forms are defeasible: a conclusion may be defeated by new knowledge, even if the premises on which the conclusion was based are not defeated. For instance, the argument `birds typically fly; Tweety is a bird; therefore, Tweety flies' is non-deductive, since Tweety might be an ostrich, hence non-typical. The argument `every day during my life the sun rose; I don't know of any trustworthy report of the sun not rising one day in the past; therefore, the sun will rise every future day' is non-deductive, since if the sun would not rise tomorrow, this would invalidate the conclusion but not the premises.

The Tweety-argument is a well-known example of what I call plausible reasoning: reasoning with general cases and exceptions[5]. This terminology is not generally accepted: this form of reasoning is normally referred to as non-monotonic reasoning. A reasoning form is monotonic if, given an argument, adding a premiss cannot defeat the conclusion. In fact, this is the same property as what I called non-defeasibility above; since any non-deductive reasoning form is defeasible, it follows that any non-deductive reasoning form is non-monotonic. In other words, the property of non-monotonicity is of limited use in classifying reasoning forms; for this reason I prefer a different (and more meaningful) term. Typically, plausible reasoning encompasses deductive reasoning, but also tries to draw, in the absence of crucial information, conclusions that are not deductively justified. In this sense plausible reasoning is `supra-deductive' or, as I will call it, quasi-deductive.

The second argument above, concerning the prediction of sunrise, is an example of induction, which is commonly defined as reasoning from specific observations (also called evidence) to general rules or hypotheses. As a first attempt this is an acceptable definition, but note that it leaves the logical relation between observations and inductive hypothesis unspecified. After all, after observing 100 white swans we might conclude that swans may have any colour. Few people would accept this inductive conclusion, but why is this so? Like with deductive reasoning this should be based on some notion of `inductive validity'. This is exactly the subject of this thesis, although I will eschew the term `validity' because of its strong deductive connotation. Note that inductive reasoning does not comprehend all deductively valid arguments and is therefore not quasi-deductive; I will call reasoning forms that do not aim at approximating deduction a-deductive.

Abduction is a term originally introduced by C.S. Peirce to denote the process of forming an explanatory hypothesis given some observations (a hypothesis from which the observations can be deduced). According to the view defended in this thesis, inferring a general explanation of observations is one possible form of inductive reasoning, so we might say that abduction is a special case of induction. However, in recent years a different notion of abduction has emerged in the logic programming field, according to which the general explanation is known, but one of its premises is not known to be true; abduction is then seen as hypothesising this missing premiss. As a consequence, abduction and induction are viewed as complementary: induction infers the general rule, given that its premises and its conclusion hold in specific cases; abduction infers specific premises, given the general rule, and specific instances of its conclusion and some of its premises. In this thesis I will stick to the former interpretation of abduction, as originally intended by Peirce; in order to minimise confusion I will mostly avoid the term abduction in favour of the term explanatory reasoning.

Explanatory reasoning is meant to formalise one aspect of inductive reasoning, namely that inductive hypotheses should be able to explain the observations. Confirmatory reasoning formalises another intuitive aspect of induction, that is, the idea that the inductive conclusion should be confirmed by the hypothesis. One might expect that the ideal inductive hypothesis is both explanatory and confirmed; however, straightforward logical formalisations of both aspects turn out to interfere in such a way that they have been developed separately in this study. Neither of these formalisations is intended to fully capture the essence of inductive reasoning; therefore, I tend to avoid the term induction in the more formal parts of the thesis, and adopt the more neutral term conjectural reasoning; the term conjecture is used synonymously with `hypothesis' in the sense of `defeasible general rule'.

Logical preliminaries



The thesis consists of three parts: Backgrounds, Foundations, and Practice. A brief overview of the chapters in each of these parts follows.


In the first part work in philosophy, logic, and artificial intelligence that is relevant for the present investigations is reviewed. The choice of works is subjective, and no claim is made as to the completeness of these overviews. On the contrary, I often concentrate on one or two authors whose work has inspired mine. Apart from some minor terminological adjustments, which I have permitted myself with a view to overall consistency[9], I have tried to remain as faithful as possible to the original author's views and intentions. Where I have felt the need to comment on or voice disagreement with those views I have done so in a separate discussion section at the end of the chapter.

In the first chapter in this part, The philosophy of induction, I discuss the philosophical backgrounds of this study. I concentrate on philosophers who have studied induction from a logical perspective, most notably Peirce and Hempel. The work of Carnap on confirmation measures is briefly reviewed in the discussion section, since it provokes some reflections on the aims and scope of logic (further dealt with in chapter 5). However, his numerical approach is not seen as fundamental to the subject of this thesis, since it does not provide any insight into the logic of induction. The main conclusion drawn from this chapter is that the dichotomy between explanatory and confirmatory induction proposed and defended in this thesis is already present, albeit implicit, in the work of Peirce and Hempel.

The next chapter is called Approaches to computational induction. It draws upon work in machine learning (a subfield of artificial intelligence) on inductively learning concepts, logic programs, and logical theories from examples. I indicate how the latter two problems can be reformulated as problems of explanatory and confirmatory induction, respectively.

The third and final chapter in the first part, The analysis of non-deductive reasoning, is mainly devoted to one article by Kraus, Lehmann and Magidor that provided the main inspiration for my work. In that article the authors set out to "study general patterns of nonmonotonic reasoning". The main tool they used for that study is the notion of a consequence relation, which is a set of pairs of premiss and conclusion, originally proposed by Gabbay. By formulating and combining properties of such consequence relations, such as (Cautious) Monotonicity and Transitivity, they succeeded in providing a systematic and precise overview of different forms of plausible reasoning, that is, a descriptive theory of plausible reasoning. In this thesis I have set out to do the same for induction.


The second part makes up the core of this thesis. It consists of three, increasingly technical, chapters. The first chapter, Outline of a descriptive theory of induction, is probably the most speculative among them, challenging some established dogmas of logic. Specifically, I take issue with the idea that a logical semantics is necessarily based on the notion of truth. In my view, any quality worth preserving in an argument may give rise to a logic formalising some useful form of reasoning. Two of the qualities that may be preserved in inductive arguments are explanatory power and regularity of interpretations[10]. Since the preservation of such qualities may not be reserved for inductive reasoning, nor characterise it completely, I introduce the term `conjectural reasoning' for any form of reasoning involving uncertain hypotheses, including induction.

In the next chapter, Properties of conjectural consequence relations, I commence my study of general patterns of conjectural reasoning in the spirit of Kraus et al. Starting with the adequacy conditions for a material definition of the relation of confirmation formulated by Hempel, I propose a number of rules for explanatory and confirmatory reasoning, and some rules that are meaningful in both cases. Systems of such rules are studied and semantically characterised in the final chapter in this part, Rule systems for conjectural reasoning.


Of the two forms of induction studied in this thesis, explanatory induction and confirmatory reasoning, the latter is certainly much less understood than the former. In the third and last part of this thesis I illustrate the practice of confirmatory induction in the context of relational databases. This chapter also illustrates my claim that in confirmatory induction one needs an additional goal which the inductive hypothesis is meant to fulfil, since `being confirmed' is not an end in itself. Those readers who wish to have a concrete idea of confirmatory induction could read this chapter before diving into the formalities of the Foundations part.

The thesis is ended with a chapter recapitulating the main achievements and conclusions, and with a few appendices including a glossary of terms and logical rules.

[1]The psychological aspects of induction fall outside the scope of this thesis.

[2]I regard artificial intelligence as a subfield of computer science rather than cognitive science -- for a collection of views on this subject see (Flach & Meersman, 1991).

[3]It may have to be approximated, or limited to special cases, because of undecidability or complexity problems, but this leaves the main point unaffected.

[4]I don't think that the field of logic, in its current state, has developed very well towards this goal. Most of the logics around, such as modal, temporal, partial and relevance logics, are mostly variations upon a theme, the theme of deductive reasoning, and thus represent only a tiny subspectrum of the huge range of possible reasoning forms. Like algebra has generalised the properties of numbers into such abstract concepts as groups, rings and fields, logic should investigate what properties of deductive logic are contingent and could be different, and what properties are tied to the nature of logic, expressing an inherent quality of reasoning. Such investigations belong to the discipline of descriptive logic.

[5]Default reasoning would be a good term, but this seems too strongly connected to a particular logic, i.e. default logic.

[9]all of which are indicated in footnotes.

[10]A third one, generality, is briefly considered but not worked out in this thesis.

P A Flach, Peter.Flach@bristol.ac.uk. Last modified on Monday 16 February 1998 at 10:44. © 1998 University of Bristol