Coherence of Laws

1 Introduction

This extended summary highlights the main points of the pa­ per, a full version [Kwok, et.al. 03] of which can be obtained electronically. This section motivates the problem and subse­ quent sections outline the definitions which formalize the in­ tuitions behind coherence, describe some properties that flow from these definitions, and provide examples of their use.

Scientific theories evidently comprise Jaws that use vocab­ ularies that contain terms which on the one hand refer to ob­ servations, and on the other refer to postulated or theoretical entities that are not directly observable. It is in fact quite common for two theories Tl and T2 that agree on the sta­ tus of their observational terms to differ in their theoretical terms. One way to compare Tl and T2 is to say that Tl is

*Supported in part by the Australian Research Council.

Abhaya C. Nayak

Knowledge Systems Group School of MPCE Macquarie University NSW 2109 Australia

more coherent than T2 if in accounting for the observations the formulas in Tl "work together better" than those in T2, or are "more useful" than in T2. A persuasive advocate for such properties is Bonjour [Bonjour 85]. In a previous paper [Kwok, et.al. 98] we proposed a definition that amounted to a quantitative measure of coherence of theories. In this paper we elaborate on the definition, repairing its deficiencies and extending its range of application.

2 Coherence

Definition 1 (Supports for Observations) Given an input set I and and output set 0, a subset r ofT is a !-relative support for a set 0 of observations if

1. r accounts for 0, i.e., r u IF a for each 0'. E 0;
2. r is minimal, i.e, for no~ c r does~ account for 0 .

Let S(T, I, 0) denote the set of all I -relative supports for 0.

This definition differs from that in [Kwok, et.al. 98] in the relativisation of notion of support to the input set I , which better models scientific practice.

Assumption 1 (Clausal Basis Assumption) All bases of theories are clauses.

Lemma 1 (Some Properties of S(T,I,O)) Fix observation sets I and 0, and let T1 ~ T2 be theories.

1. Monotonicity in T: S(TI. I, 0) ~ S(T2, I, 0)
2. T1 u IF 0 i.ff3 r ~ T1 such that r E S(T2 , I , 0).

Fix observation set I and theory T. Let 01 ~ 02 be observation sets. Then for every f2 E S(T, I, 02) there is a f1 E S(T, I, 01) such that f1 ~ f2.

Fix observation set 0 and theory T. Let h ~ h be observation sets. Then for every f1 E S(T, I, 01) there is a f2 E S(T, I, 02) such that f2 ~ f1.

Definition 2 (Utility of a Formula) The Utility of a formula ex, if S(T, I, 0) =/= 0, in a theory T with respect to an ]­ relative observation set 0 is:

Informally, this is the relative frequency of occurence of a in the support sets for 0.

Definition 3 (Coherence of a Theory) LetT be a finite theory { a1, ... , an}. I a finite sequence of (input) observations (h, h , ... Im) and 0 a finite sequence of (output) observations (01, . .. , Om)· The !-relative coherence ofT with re­ spect to 0 is:

Informally, coherence is the average utility of the elements ofT in supporting some observations with the help of others. The inputs do not figure directly in the counting because it is the internal laws (or rules) ofT that we are assessing for how the outputs are supported.

3 A Typical Application

In the full paper there are applications of the above defini­ tions to (i) demolish Craig's Trick [Craig 53], alleged by some to show that theoretical terms are unnecessary, by demon­ strating that it yields highly incohrent theories; (ii) argue that Mendel's assumption of two independent theoretical charac­ teristics to account for the observations of his pea plant ex­ periments yields a highly coherent theory; and (iii) indicate that programs that realize the Kolmogorov complexity of se­ quences are maximally coherent. Here we focus on a typical application and its implication for coherence of modular the­ ories.

3.1 The Black Swan Fix

Prior to western ornithologists exploration of Australia all the swans they had hitherto encountered were white in color. For this focussed domain, there is only one type of object, namely swans, that are of interest. The observational predicates are swan and white, and we regard the former as the input and the latter as the output. A succinct way to capture induction is the rule 1 in the theory T below:

Notice that T does not have any theoretical terms as we have specified that both the predicates are observational. In Australia they saw black swans. Here is an ad hoc way to revise T minimally if we can enumerate these black swans as additions to the original input set, i.e. these new swans are sw1 , sw2, ... , swn. Call this fix Tn. The revised rules that replace rule 1 are:

(1 sentence)

and (2n sentences)

Suppose the new observation terms are about swan color, i.e., black or white.

Tn has 2n+ 1 sentences. For any finite set of k black swans, there are exactly 2k sentences in Tn that support their color.

Each such support sentence has utility 1 for a particular swan swi, and 0 for other swans.

Hence the coherence of Tn for such k observations is 2 ~~ 1 , which is asymptotically 0 with large n . This is an argument against the fix. The "good" fix is what happens in inductive learning when a predicate is invented to summarize the discovery that black swans live in Australia, viz., the new theory T' wit 2 sentences

The input set I now comprises pairs of the swan atoms and the new observable Australian literals. The output 0 are the two color terms white and black. Now for any one swan (call it c) observation, its color is supported either by the formulas 4 and -.Australian(c), or by the formulas 5 and Australian( c). Therefore, irrespective of the color the sup­ port set for each observation has cardinality 2. Suppose there are k1 white and k2 black swans in an observation sequence. It is then easy to see that the utilities of formula 4 is 1 for k1 observations but 0 for the k2 observations; formula 5 is the dual of the preceding. The coherence of this theory for any k1 + k2 swans is therefore ~.

3.2 Modularization and Coherence

In the above example, suppose we partition the output obser­ vational terms into black (swans) and white (swans), denot­ ing the disjoint sets by Ob and Ow respectively. Likewise, we partition the input set into two, h and l w denoting the pairs of hypothesized Australian literal and swan atom. Then it is not hard to see that the formula 4 is in all support sets of S(T', Iw, Ow), but is not in any support set of S(T', h, Ob) · Dually, the formulaS is in all support sets of S(T', h, Ob) but in none of those of S(T', Iw, Ow)· The utility of each formula is 1 in their respective support sets, and 0 in the other. This is about as strong as we can get in modularizing a theory.

This idea has the following obvious generalization. Sup­ pose an observation set to be accounted for can be partitioned into { 0 1 , .. . , On} and the theory r has invented theoretical terms { 'Yt, . . . , 'Yn}, such that for each i, ')'; is in every set of S(r, I, 0;). Then the')'; modularize the theory r with respect to the observation partitions.