Notes

The earliest sophisticated attempt at clarifying the connection between objective statistical knowledge and degrees of belief, and the basis for most subsequent proposals involving reference classes, is due to Reichenbach [1949]. A great deal of further work has been done on reference classes, perhaps most notably by Kyburg [1974; 1983] and Pollock [1990]; this work mainly elaborates the way in which the reference class should be chosen in case there are competing reference classes.

The random-worlds approach was defined in [Bacchus, Grove, Halpern, and Koller 1996]. However, the key ideas in the approach are not new. Many of them can be found in the work of Johnson [1932] and Carnap [1950; 1952], although these authors focus on knowledge bases that contain only first-order information and, for the most part, restrict their attention to unary predicates. More recently, Chuaqui [1991] and Shastri [1989] have presented approaches similar in spirit to the random-worlds approach. Much of the discussion in this chapter is taken from [Bacchus, Grove, Halpern, and Koller 1996]. Stronger versions of Theorems 11.3.2, 11.3.7, and 11.3.8 are proved in the paper (cf. Exercises 11.6 and 11.10). More discussion on dealing with approximate equality can be found in [Koller and Halpern 1992].

Example 11.3.9, due to Reiter and Criscuolo [1981], is called the Nixon Diamond and is one of the best-known examples in the default-reasoning literature showing the difficulty of dealing with conflicting information. Example 11.4.4 is due to Poole [1989]; he presents it as an example of problems that arise in Reiter's [1980] default logic, which would conclude that both arms are usable.

The connections to maximum entropy discussed in Section 11.5 are explored in more detail in [Grove, Halpern, and Koller 1994], where Theorem 11.5.1 is proved. This paper also provides further discussion of the relationship between maximum entropy and the random-worlds approach (and why this relationship breaks down when there are nonunary predicates in the vocabulary). Paris and Venkovska [1989; 1992] use an approach based on maximum entropy to deal with reasoning about uncertainty, although they work at the propositional level. The observation that the maximum-entropy approach to default reasoning in Section 8.5 leads to some anomalous conclusions as a result of using the same ∊ for all rules is due to Geffner [1992a]. Geffner presents another approach to default reasoning that seems to result in the same conclusions as the random-worlds translation of the maximum-entropy approach when different approximate equality relations are used; however, the exact relationship between the two approaches is as yet unknown. Stirling's approximation to m! (which is used in Exercise 11.16) is well known; see [Graham, Knuth, and Patashnik 1989].

Problems with the random-worlds approach (including ones not mentioned here) are discussed in [Bacchus, Grove, Halpern, and Koller 1996]. Because of the connection between random worlds and maximum entropy, random worlds inherits some well-known problems of the maximum-entropy approach, such as representation dependence. In [Halpern and Koller 1995] a definition of representation independence in the context of probabilistic reasoning is given; it is shown that essentially every interesting nondeductive inference procedure cannot be representation independent in the sense of this definition. Thus the problem is not unique to maximum entropy (or random worlds). Walley [1996] proposes an approach to modeling uncertainty that is representation independent, using sets of Dirichlet distributions.

A number of variants of the random-worlds approach are presented in [Bacchus, Grove, Halpern, and Koller 1992]; each of them has its own problems and features. The one presented in Exercise 11.19 is called the random-propensities approach. It does allow some learning, at least as long as the vocabulary is restricted to unary predicates. In that case, as shown in [Koller and Halpern 1996], it satisfies analogues of Theorem 11.3.2 and 11.3.7. However, the random-propensities method does not extend too well to nonunary predicates.