[ Bristol CS | Index | ML group | Peter Flach | Papers | Presentations | PhD thesis ] 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.
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.
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.
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.
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'.
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.
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.
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.
[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.