Representation Dependence in Probabilistic Inference

1 Introduction

It is well known that the way a problem is represented can have a significant impact on the ease with which people solve it, and on the complexity of an algorithm for solving it. We are interested in what is arguably an even more fundamental issue: the extent to which the answers that we get depend on how our input is represented.

To make our discussion more concrete, we discuss this issue in one particular context: probabilistic inference. We focus on probabilistic inference both because of the recent in­ terest in using probability for knowledge representation (e.g., [Pearl, 1988]) and because it has been the source of many of the concerns expressed regarding representation. However, our approach should be applicable far more generally.

Suppose we have a procedure for making inferences from a probabilistic knowledge base. How sensitive is it to the way knowledge is represented? Consider the following examples, which use perhaps the best-known non-deductive notion of

*Research sponsored in part by the Air Force Office of Scien­ tific Research (AFSC), under Contract F49620-91-C-0080, and by a University of California President's Postdoctoral Fellowship.

Daphne Koller

Computer Science Division University of California, Berkeley Berkeley, CA 94720 daphne@cs.berkeley.edu

probabilistic inference, maximum entropy [Jaynes, 1978]. 1

Example 1.1: Suppose we have no information whatsoever. What probability should we assign to the proposition coloiful? Symmetry arguments might suggest 1/2: Since we have no information, it seems that an object should be just as likely to be colorful as non-colorful. This is also the conclusion reached by maximum entropy. But now suppose we consider a more refined view of the world where we have colors, and by coloiful we actually mean red V blue V green. In this case, maximum entropy dictates that the probability of red V blue V green is 7/8. Note that, in both cases, the only conclusion that follows from our constraints is the trivial one: that the probability of the query is somewhere between 0 and 1. I

Example 1.2: Suppose we are told that half of the birds fly. There are two reasonable ways to represent this infor­ mation. One is to have propositions bird and fly, and use a knowledge base KJiiY =ctef [Pr(fiy I bird) = 1/2]. A sec­ ond might be to have as basic predicates bird and flying-bird, and use a knowledge base KII/ =ctef [(fiying-bird => bird) 1\ Pr(fiying-birdl bird) = 1 /2]. Although the first representation may appear more natural, it seems that both representations are intuitively equivalent insofar as representing the informa­ tion that we have been given. But if we use an inference method such as maximum entropy, the first representation leads us to infer Pr( bird) = I /2, while the second leads us to infer Pr( bird) = 3/4. I

Examples such as these are the basis for the frequent criticisms of maximum entropy on the grounds of repre­ sentation dependence. But other than pointing out these examples, there has been little work on this problem. In fact, other than the work of Salmon [Salmon, 1961; Salmon, 1963], there seems to have been no work on for­ malizing the notion of representation dependence. One might say that the consensus was: "whatever representation inde­ pendence is, it is not a property enjoyed by maximum en­ tropy." But are there any other inference procedures that have it? In this paper we attempt to understand the notion of rep­ resentation dependence, and to study the extent to which it is achievable.

1 Although much of our discussion is motivated by the represen­ tation dependence problem encountered by maximum entropy, an understanding of maximum entropy and how it works is not essen­ tial for understanding our discussion.

To study representation dependence, we must first under­ stand what we mean by a "representation". The real world is complex. In any reasoning process, we must focus on certain details and ignore others. At a semantic level, the relevant distinctions are captured by using a space X of possible al­ ternatives or states. In Example 1.1, our first representation focused on the single attribute colorful. In this case, we have only two states in the state space, corresponding to colorful being true and false, respectively. The second representation, using red, blue, and green, has a richer state space. Clearly, there are other distinctions that we could make. At a syntactic level , we often capture relevant distinctions using some for­ mal language. For example, if we use propositional logic as our basic knowledge representation language, our choice of primitive propositions characterizes the distinctions that we have chosen to make. In this case, we can take the states to be truth assignments to these propositions. Similarly, if we use belief networks [Pearl, 1988] as our knowledge representation language, we must choose some set of relevant variables. The states are then then possible assignments of values to these variables.

What does it mean to shift from a representation (i.e., state space) X to another representation Y? For us, this amounts to associating subsets of X with subsets of Y. Thus, for ex­ ample, the state where colorful holds can be associated with the set of states where either red, blue, or green holds. We capture the notion of representation shift formally by em­ beddings. An embedding f from X to Y maps subsets of X to subsets of Y in a way that preserves complementa­ tion and intersection. An embedding is just the semantic version of the standard logical notion of interpretation [En­ derton, 1972, pp. 157-162], which has also been used in the recent literature on abstraction [Giunchigliaand Walsh, 1992; Nayak and Levy, 1994]. Essentially, an interpretation maps formulas in a vocabulary <I> to formulas in a different vo­ cabulary 'I' by mapping the primitive propositions in <I> (e.g., colorful) to formulas over 'I' (e.g., redV blueV green) and then extending to complex formulas in the obvious way. The rep­ resentation shift in Example 1.2 can also be captured in terms of an interpretation, this one takingflying-bird to fly 1\ bird.

When doing probabilistic reasoning, we are actually in­ terested in the probability of the various states in X. We therefore assume that a user's knowledge base KB consists of a set of probabilistic assertions, such as Pr(fly I bird) = 1/2, that place constraints on distributions over X. A representa­ tion shift from X to Y induces a corresponding shift >from information about X to information about Y. More formally, an embedding f from X to Y can be extended to a mapping f* from constraints on distributions over X to constraints over distributions over Y in a straightforward way. For example, if the embedding f maps colorful to red V blue V green, then f* (Pr(colorful) ?: 2/3) is Pr(red V blue V green) ?: 2/3.

A probabilistic inference procedure f-v takes a probabilis­ tic knowledge base and uses it to reach conclusions about the probability of various events over the space X. Such a pro­ cedure is said to be invariant under f if f does not change the conclusions that we make; that is, if for any KB and (), KB f"--() iff f(KB) f-v f(B). Roughly speaking, f-vis represen­ tation independent if it is invariant under all embeddings. This captures the intuition that f-v gives us the same answers no matter how we shift representations. Of course, not all embeddings count as legitimate representation shifts. For example, consider an embedding f defined in terms of an interpretation that maps both the propositions p and q to the proposition r. Then the process of changing representations using f gives us the information that p and q are equivalent, information that we might not have had originally. Intuitively, f gives us new information if it tells us that certain situations-e.g., those where p 1\ ·q holds-are not possible. Formally, f is said to be faithful iff ( { x}) :{; 0 for all x E X. We show that f is faithful if and only if for any KB and(), the assertion B necessarily follows from I<B if and only iff(()) follows from f(I<B). That is, faithful embeddings are precisely those that give us no new information.

At first glance, representation independence seems like a reasonable desideratum. However, as we show in Section 3, it has some rather unfortunate consequences. In particular, we show that any representation independent inference procedure must act essentially like logical entailment for a knowledge base with only non-probabilistic information. In fact, if we also require that our inference procedure ignore blatantly irrel­ evant information, then it must act like logical entailment for every knowledge base. Finally, representation independence is completely incompatible with even the simplest default as­ sumption of independence: Even if we are told nothing about the basic propositions p and q, representation independence does not allow us to jump to the conclusion that p and q are independent.

This seems to put us in a rather awkward situation: It seems we must either give up on representation independence, or make do with an inference procedure that is essentially incapable of even minimal inductive reasoning (jumping to conclusions). But things are not quite as bleak as they seem. In practice, we would claim that the choice of language does carry a great deal of information. That information is what gives us the intuition that certain embeddings are legitimate, while others that have the same abstract structure are not. For example, suppose that certain propositions represent colors while others represent birds. While we may be willing to transform colorful to red V blue V green, we may not be will­ ing to transform red to fly. There is no reason to demand that an inference procedure behave the same way if we sud­ denly shift to a wildly inappropriate representation, where the symbols mean something completely different. Given a class of "appropriate" embeddings (where the notion of appropri­ ate might be application-dependent), we may well be able to get an interesting notion of representation independence with respect to that class.

In Section 5, we provide a general approach to constructing inference procedures that are invariant under a specific class of embeddings. We assume that the user starts with some set of initial prior probability distributions that characterize his beliefs in the absence of information. We show that if the prior distributions are chosen appropriately, so that they are invariant under the class of embeddings of interest, then we can "bootstrap" up to obtain a general inference procedure that is invariant under the same class of embeddings, by us­ ing cross-entropy [Kullback and Lei bier, 1951], a well-known generalization of probabilistic conditioning. This result can be used in a number of ways. For example, it shows us how to construct an inference procedure that is invariant under a given set of embeddings: we simply choose a class of priors appropriately. It also allows us to combine some degree of representation independence with certain non-deductive prop­ erties that we want of our inference procedure. We simply choose a class of priors that has the desired property, and determine the set of embeddings under which this class of priors is invariant. We demonstrate this process by present­ ing an inference method that supports a default assumption of independence, and yet is invariant under a natural class of embeddings.

2 Probabilistic Inference

We begin by defining probabilistic inference procedures. Such a procedure takes as input a probabilistic knowledge base and returns a probabilistic conclusion. We express this in a semantic framework that we hope can be understood by both logicians and probabilists.

We take both the knowledge base and the conclusion to be probabilistic assertions about the probabilities of events over some state space X. Formally, these can be viewed as statements (or constraints) on distributions over X. For example, if A is a subset of X, a statement Pr(A) 2 2/3 holds only for distributions where A has probability at least 2/3 . Therefore, if !lx is the set of all probability distributions on X, we can view a knowledge base as a set of constraints over !lx. We place very few restrictions on the language used to express the constraints. All that we require is that the language is closed under conjunction and negation, so that if KB and I<B' are knowledge bases expressing constraints, then so are I<B 1\ KB' and -,](B. Given a knowledge base I<B placing constraints on !lx, we write 11 f= KB if 11 is a distribution in !lx that satisfies the constraints in KB, and we let [I<B]x denote all the distributions satisfying these constraints. We say that I<B is consistent if [I<B]x =f 0, i.e., if the constraints are satisfiable. Finally, we say that I< B entails e (where e is another set of constraints on !lx ), written I<B f=x e, if [I<B]x ~ [e]x, i.e., if every distribution that satisfies I<B also satisfies e. We write f=x e if e is satisfied by every distribution in !lx . We omit the subscript X from f= if it is clear from context.

Entailment is well-known to be to be a very weak method of drawing conclusions from a knowledge base. For exam­ ple, it is unable to ignore irrelevant information. Consider the knowledge base Pr(jly I bird) 2 0.9. Even though we know nothing to suggest that red is at all relevant, entailment will not allow us to reach any nontrivial conclusion about Pr(jly I bird 1\ red). One way to get more powerful conclu­ sions is to consider, not all the distributions that satisfy I<B, but a subset of them. Intuitively, given a knowledge base I<B, an inference procedure picks a subset of the distributions satisfying I<B, and infers e if e holds in this subset.

Definition 2.1: An X -inference procedure is a function Ix : 2Ax f-t 2Ax such that Ix (A) ~ A for A ~ !lx and Ix (A) = 0 iff A= 0. We write KB f-Ixe if Ix([KB]x) ~ [e]x.l

We are typically interested in X -inference procedures not just for one space X, but for a family X of spaces. In cases where X EX is clear from context, we writei<B f-Ie, omitting the subscript X. Clearly entailment is an X -inference procedure for any X, where Ix is simply the identity function. Another well-known inference procedure is maximum entropy, which picks out of [ KB]x the subset of the distributions having the maximum entropy.

Example 2.2: Given a distribution 11 over a finite space X, its entropy H(11) is defined as- ExEX 11(x) log11(x) . Given a set A of distributions in !lx , let I)(e( A) consist of the distribu­ tions in A that have the highest entropy. I'j(e clearly defines an inference procedure, which we denote f-me . Thus, KB f-me e if e holds in all the distributions of maximum entropy satisfy­ ing KB.I

There are, of course, many other inference procedures. In fact, as the following proposition shows, any binary relation f- satisfying certain reasonable properties is an inference procedure of this type.

Proposition 2.3: I is an X -inference procedure if and only if the following properties hold for every KB, KB' , i.p, 1/J over X :

• Reflexivity: KB f-I KB.
• Left Logical Equivalence: if KB is logically equivalent toKE', i.e., iff= KB <:> KB', thenKB he ijfKB' he.
• Right Weakening: if KB f-I e and f= e => 1/J then KBh 'I/J.
• And: if KB he and KB h 1/J, then KB h 8 1\ 1/J.
• Consistency: if KB is consistent then KB ff 1 false. I

Interestingly, these properties are commonly viewed as part of a core of reasonable properties for a nonmonotonic inference relation [Kraus et al., 1990].

Although our basic framework puts no constraints on the state space X and very few constraints on the language used to describe constraints, in practice, we often use a logical language to describe the possible states, and this language then determines the state space. Typical languages include propositional logic, first-order logic, or a language describing the values for some set of random variables. In general, a base logic £ defines a set of formulas £ ( <l>) for a given vocabulary <l>. In propositional logic, the vocabulary <l> is simply a set of propositional symbols. In probability theory, the vocabulary can consist of a set of random variables. In first-order logic, the vocabulary is a set of constant symbols, function symbols, and predicate symbols. For simplicity, we assume that for each base logic all the vocabularies are finite subsets of one fixed infinite vocabulary <l>*. Each state in our state space defines an interpretation for the symbols in <l>. Hence, in the case of propositional logic, a state can be viewed as a model over <l>: a truth assignment to the primitive propositions; for first-order logic, a state consists of a domain and an interpretation of the symbols in <l>; in the probabilistic setting, a state is an assignment of values to the random variables. In this case, we often take our state space to be W(<l>), the set of all models (or assignments) over the vocabulary <l>, or some subset of it. Note that the truth of any formula l.fJ in £ ( <l>) is determined by a state. If l.fJ is true in some state w, we write w f= i.p. We call formulas in the base language objective. Objective formulas can be thought of as describing events.

The probabilistic extension £P'( <l>) of a base logic£( <l>) is simply the set of probability formulas over £(<1>). Formally, for each l.fJ E £ ( <l>), Pr( l.fJ) is a numeric term. The formulas in £P'(<l>) are defined to be all the Boolean combinations of arithmetic expressions involving numeric terms. For example, Pr(jly I bird) 2 1/2 is a formula in £P'( {fly , bird}) (where we interpret a conditional probability expression Pr( t.p 11/J) as Pr( t.p 1\ 1/;) / Pr( 1/;) and then multiply to clear the denominator). We ascribe semantics to £P'( <l>) via a probability distribution fL over W( <l>) . We interpret the numeric term Pr( cp) as JL( { w E W( <l>) : w I= t.p} ). Since an objective formula cp describes an event over the space X, a formula Bin £P'(<l>) is clearly a constraint on distributions over X. We write fL I= B if the distribution fL satisfies the formula B. Note that £P' does not contain objective formulas; we interpret the notation fL I= t.p for an objective formula cp as an abbreviation for fL I= Pr( t.p) = 1. Thus, an objective formula corresponds to a constraint of a special form, that says a particular event is certain.

3 Representation independence

As we discussed in the introduction, we capture the idea of a representation shift using the notion of an embedding. If X and Y are two different representations, then an embed­ ding from X to Y reflects the correspondence of the states in X and the states in Y. This embedding should respect the logical structure of events. Formally, we require that it be a homomorphism with respect to conjunction and negation.

Definition 3.1: An embedding f from X to Y is a function f : 2x t-T 2Y such that f(A n B) = f(A) n f(B) and f(A) = f(A) for all A, B ~X. I

Clearly, an embedding f induces a map f* : 2"'x I-T 2"'Y defined as follows: f*(JL) = {v E ~Y : v(f(S)) p(S) for all S ~X} and f* (A) = UJJEAf* (p). 2

Example 3.2 : In Example 1.1, we might have X = {colorful , colorful} and Y = {red, blue, green, colorful}. In this case, we might have !(colorful) = {red , blue, green} and f( colorful) = {colorful} . Consider the distribution fL E ~X such that p(colorful) = 0.7 and p(colorful) = 0.3. Then f* (JL) is the set of distributions v such that the total probabil­ ity assigned to the set of states {red, blue, green} by vis 0.7. Note that there are uncountably many such distributions. I

Em beddings can be viewed as the semantic analogue to the notion of interpretation defined in [Enderton, 1972].

Definition 3.3: Let <l> and ~ be two vocabularies. In the propositional case, a interpretation of <l> into~ is a function i that associates with every propositional symbol p E <l> a formula i(p) E £(~). A more complex definition in the same spirit applies to first-order vocabularies. For example, if R is a k-ary predicate, then i(R) is a formula with k free variables.

I

Given an interpretation i, we get a syntactic translation from formulas in £(<1>) to formulas in£(~) using i in the obvious way; for example, i((pl\ ·q) Vr) = (i(p) 1\ · i(q)) Vi(r) (see [Enderton, 1972] for the details). Clearly an interpretation i from <l> to~ induces an embedding from W(<l>) toW(~) (at least, from the sets of models definable by formulas): we map [cp]<1>-the set of states in W( <l>) satisfying cp-to [i( cp )]'!'­ the set of states in W(~) satisfying i( cp) .

If the embedding f is a "reasonable" representation shift, we would like an inference procedures to return the same answers if we shift representations using f .

2 Strictly speaking, we should write f ( {p} ), not f(p). However, here and elsewhere we omit set braces around function arguments that are singleton sets.

Definition 3.4: We say that I is invariant under f if for all constraints KB and B, we have KB f-.- 1 B iff f* ( KB) f-.- I f* (B).

I

As we argued in the introduction, not every embedding is appropriate as a representation shift. The process of changing representation should not give us any new information. When does a shift give us new information? One obvious situation is when the shift makes impossible something which we con­ sidered to be possible. In our example from the introduction, we had an interpretation i with the property that i(p) = i(q) for two propositions p and q. Clearly, this interpretation gives us new information: that p and q are equivalent. Semanti­ cally, the associated embedding f has the following undesir­ able property: it maps the set of states satisfying p 1\ ·q to the empty set. This means a state where p 1\ .,..,q holds does not have an analogue in the new representation. We want to disallow such embeddings.

Definition 3.5: We say that an embedding f : X I-T Y is faithful if for any x EX, f(x) -f. 0. I

This has the desired consequence of not giving us new information:

Lemma 3.6: An embedding f : X I-T Y is faithful if and only if for all constraints KB and (), we have KB I= B iff f*(KB) I= f*(B).

It is clear that our embedding from Example 3.2 is faithful: f (colorful) = {red , blue, green} and f( colorful) = colorful. Therefore, an inference procedure which is invariant under all faithful embeddings would return the same answers for Pr( colorful) as for Pr(red V blue V green).

The issue is somewhat more subtle for Example 1.2. There, we would like to have an embedding f generated by the inter­ pretation i(jlying-bird) =fly 1\ bird and i(bird) = bird. This is not a faithful embedding, since flying-bird => bird is not a valid formula, while i(jlying-bird => bird) is (fly 1\ bird) ::} bird which is valid. Looking at this problem semantically, we see that the state corresponding to the model where flying-bird 1\ ·bird holds is mapped to 0. But this is clearly the source of the problem. According to our linguistic intu­ itions for this domain, this is not a "legitimate" state. Rather than considering all the states in W( {flying-bird, bird}), it is perhaps more appropriate to consider the subset X con­ sisting of the truth assignments characterized by the formulas {flying-bird 1\ bird, -.jlying-birdl\ bird, -.jlying-birdl\ ·bird}. If we now use ito embed X into W( {fly , bird}), the resulting embedding is indeed faithful. So, as for the previous example, invariance under this embedding would guarantee that we get the same answers under both representations.

Definition 3.7: We say that f-.- I is representation independent if f-.-I is invariant under all faithful embeddings. I

Are there any representation independent inference proce­ dures? It follows trivially from Lemma 3.6 that entailment is representation independent. Are there others? As we now show, any such inference procedures are unlikely to be inter­ esting.

We say that an inference procedure I is essentially en­ tailment for I<B if I<B h a < Pr(cp) < f3 implies I<B F= a :::; Pr( t.p) :::; {3. Thus, when entailment lets us conclude Pr( cp) E [a , {3], an inference procedure that is essentially en­ tailment lets us draw only the slightly stronger conclusion Pr( t.p) E (a, /3).

Theorem 3.8: Every representation independent inference procedure is essentially entailment for every objective KB.

This result tells us that from an objective knowledge base KB-one asserting only that certain events are known to be true-we can reach only three possible conclusions about another event 'P· If 'P is entailed by the KB, we conclude Pr( 'P) = 1; if -,'Pis entailed by the I<B , we conclude Pr( 'P) = 0; and if both 'P and -,'P are consistent with the KB, the strongest conclusion we can make about Pr( 'P) is that it is somewhere between 0 and 1.

This result implies that various inference procedures can­ not be representation independent. In particular, since true ~me Pr(p) = 1/2 for a primitive proposition p, it fol­ lows that ~me is not essentially entailment. It follows that maximum entropy is not representation independent.

It is consistent with this theorem that there are represen­ tation independent inference procedures that are not almost entailment for probabilistic knowledge bases. For example, as we show in the full paper, there is a representation independent inference procedure I such that (Pr(p) > 1/4) h Pr(p) > 1/2. However, as we now show, such an inference procedure is unlikely to be an interesting one. In particular, we show that if adding "irrelevant" information to the knowledge base does not affect our inferences, then every representation in­ dependent inference procedure is essentially entailment. We define "irrelevant" syntactically here; in the full paper we give the semantic analogue of the definitions. Syntactically, "irrelevant" means "in a disjoint vocabulary".

Definition 3.9: We say that ~I enforces minimal irrele­ vance if, whenever <I> and 'I' are disjoint vocabularies, KB, B E £P'(<I>) and KB' E £P'('I'), then KB hB iff KB 1\ KB' hB.

I

Minimal irrelevance certainly seems like an innocuous and reasonable property. Adding information about symbols that do not appear in either I<B orB should not affect whether we can infer B from ]{B. Logical entailment, being a monotonic inference procedure, clearly enforces minimal irrelevance. It is not hard to show that maximum entropy does too (see [Paris, 1994] for a proof). Unfortunately, minimal irrelevance com­ bined with representation independence forces us to inference procedures that are essentially entailment.

Theorem 3.10: Any representation independent inference procedure that enforces minimal irrelevance is essentially en­ tailment.

In the full paper, we show that other desirable properties are completely inconsistent with representation independence. As one example, we show that representation independence is inconsistent with a default assumption of independence. Again, we define minimal default independence syntactically here, deferring a semantic definition to the full paper.

Definition 3.11: We say that ~I enforces minimal default independence if, whenever <I> and 'I' are disjoint vocabularies, KB E £P'(<I>), 'P E .C(<I>), and '1/; E £('1'), then KB h'P iff KB h Pr('PI'l/!) = Pr(l.fJ). I

Clearly entailment does not satisfy minimal default in­ dependence. Maximum entropy, however, does. Indeed, a semantic property that implies minimal default independence is used in [Shore and Johnson, 1980] as one of the axioms in an axiomatic characterization of maximum-entropy.

Theorem 3.12: Any inference procedure that enforces mini­ mal default independence cannot be representation indepen­ dent.

4 Discussion

These results suggest that any type of representation indepen­ dence is hard to come by. They also raise the concern that perhaps our definitions were not quite right. We can provide what seems to be even more support for the latter point.

Example 4.1: Let P be a unary predicate and c1, ... , c100, d be constant symbols. Suppose that we have two vocabularies <I> = { P, d} and 'I' = { P, c1, ... , c10o, d} . Consider the interpretation i from <I> to 'I' for which i( d) = d and i( P ( x)) = P(x) 1\ P(cl) 1\ ... P(c10o) . It is fairly straightforward to verify that the embedding f corresponding to i is faithful. Intuitively, since all the c; 's may refer to the same domain element, the only conclusion we can make with certainty from P(cl) 1\ ... 1\ P(c10o) is that there exists at least one P in the domain. But we can draw this conclusion from f* (KB) only if P(x) appears positively in KB, in which case we already know that there is at least one P. But it does not seem unreasonable that an inference procedure should assign different degrees of belief to P(d) given 3xP(x) on the one hand and 3x(P(x) 1\ P(c!) 1\ . . . 1\ P(c10o)) on the other, 3 particularly if the domain is small. In fact, many inductive reasoning systems explicitly adopt a unique names assumption, which would clearly force different conclusions in these two situations. I

This example suggests that, at least in the first-order case, even faithful embeddings do not always match out our in­ tuition for a "reasonable" representation shift. One might therefore think that perhaps the problem is with our definition even in the propositional case. Maybe there is a totally dif­ ferent definition of representation independence that avoids these problems. While this is possible, we do not believe it to be the case. The techniques we used to prove Theorem 3.10 and 3.12 seem to apply to any reasonable notion of represen­ tation independence. 4 To give the flavor of the type of argu­ ments used to prove these theorems, consider Example 1.1, and assume that true ~I Pr(colorful) = a for a E (0, 1) . 5 Using an embedding g such that g(colorful) = red, we con­ clude that true ~I Pr( red) = a. Similarly, we can conclude Pr(blue) = a and Pr(green) = a. But in order for ~~ to be invariant under our original embedding, we must have true~~ Pr(red V blue V green) = a, which is completely inconsistent with our previous conclusions. But the embed­ dings we use in this argument are very natural ones; we would not want a definition of representation independence that dis­ allowed them.

But if we cannot avoid our negative results by moving to a better definition, where does that leave us? One approach is to declare that representation dependence is justified; the choice of an appropriate representation is indeed a significant one, which does encode some of the information at our disposal . In particular, it encodes the bias of the knowledge-base designer about the world. Researchers in machine learning have long realized that bias is an inevitable component of effective in­ ductive reasoning. So we should not be completely surprised if it turns out that other types of leaping to conclusions (as in our context) also depend on the bias.

3 Actually, i(P(d)) = P(d) 1\ P(c1) 1\ ... P(cHxl), but the latter is equivalent to P(d) given our knowledge base.

4 They applied to all of the many definitions that we tried.

5 1n fact, it suffices to assume that true f-- 1 Pr( colorful) E [a, ,6], as long as a > 0 or ,6 < I.

Bias and representation independence are two extremes in a spectrum. If we accept that the knowledge base encodes the user's bias, there is no obligation to be invariant under any representation shifts at all. On the other hand, if we assume the representation used carries no information, coherence re­ quires that our inference procedure give the same answers for all "equivalent" representations. We believe that the right an­ swer lies somewhere in between. There are typically a number of reasonable ways in which we can represent our informa­ tion, and we might want our inference procedure to return the same conclusions no matter which of these we choose. It thus makes sense to require that our inference procedure be invariant under embeddings that take us from one reasonable representation to another. But it does not follow that it must be invariant under all embeddings, or even all embeddings that are syntactically similar to the ones we wish to allow. We may be willing to refine colorful to red V blue V green or to define flying-bird as fly 1\ bird, but not to transform red to fly. In the next section, we show how to construct inference procedures that are representation independent under a limited class of representation shifts.

5 Selective invariance

As discussed above, we want to construct an inference pro­ cedure I that is invariant only under certain embeddings. In order to do this, it is important to understand the conditions under which I is invariant under a specific embedding f from X toY.

When do we conclude e from K B ~ I::J.x? Recall that an inference procedure I picks a subset Vx = Ix(KB), and concludes e iff e holds for every distribution in 1J X. Similarly, when applied to f* (KB) ~ !::J.y, I picks a subset 1Jy = Iy(f*(KB)) . For I to be invariant under f with re­ spect to KB, there has to be a tight connection between Vx and 1Jy . To understand this connection, first consider a pair of distributions J.1- over X and v over Y. When do these dis­ tributions generate the same probabilities for corresponding events? That is, when do we have that J.1- f= e iff v f= f* (e) for every e? Clearly, this happens if and only if J.l-(A) = v(f(A)) for any event A~ X, i.e., if v E f* (J.l-). In this case, we say that J.1- and v correspond. In order to understand how to apply this idea to sets 1J x and 1Jy, consider the following example:

Example 5.1: Consider our embedding f of Example 3.2, and let Vx = {J.l- , J.l- 1 } where J.l-(colorful) = 0.7 as in Exam­ ple 3.2, while J.l- 1 (colorful) = 0.6. How do we guarantee that we reach the corresponding conclusions from 1J x and 1Jy? Assume, for example, that 1Jy contains some distribution v that does not correspond to either J.1- or J.l- 1 , e.g., the distribu­ tion that assigns probability 1/4 to all four states. In this case, the conclusion Pr( colorful) ::=; 0.7 holds in 1J x, because it holds for both these distributions; but the corresponding con­ clusion Pr(red V blue V green) ::=; 0.7 does not hold in 7Jy . Therefore, every distribution in 7Jy must correspond to some distribution in 1J x. Conversely, every distribution in 1J x must correspond to a distribution in 7Jy. For suppose that there is no distribution v E 7Jy corresponding to J.l-. Then we get the conclusion Pr( blue V red V green) =F 0. 7 from 1Jy, but the corresponding conclusion Pr(colorful) =F 0.7 does not follow from 1J x. Note that these two conditions do not imply that 1Jy must be precisely the set of distributions corresponding to distributions in 1J x. In particular, we might have 7Jy con­ taining only a single distribution v corresponding to J.1- (and at least one corresponding to J.l- 1 ), e.g., one with v(red) = 0.5, v(blue) = 0, v(green) = 0.2, and v(colorful) = 0.3. I

We say that 1J x and 1Jy correspond under f if for all for allv E 7Jy there exists a corresponding J.1- E 1J x, and for all J.1- E 1J x, there exists a corresponding distribution v E 7Jy.

Proposition 5.2: Let f be an embedding of X into Y, and consider 1J x ~ I::J.x and 1Jy ~ !::J.y. Then 1J x f= e iff 1Jy F j* (e) for all B exactly when 1J X and 1Jy correspond under f.

We say that I is invariant under f with respect to KB if KB h B iff f* (KB) f--- 1 f* (B) for all constraints B. By definition, I is invariant under f iff it is invariant under f with respect to every KB. By Proposition 5.2, in order for I to be invariant under f, we must have a correspondence between Ix (I< B) and !y (!* ( J{ B)), for each J{ B. At first glance, it seems rather difficult to guarantee correspondence for every knowledge base. · It turns out that the situation is not that bad. In this section, we show how, starting with a correspondence for the knowledge base true-that is, starting with a correspondence between Ix(!::J.x) and !y(!::J.y )-we can bootstrap to a correspondence for all KB 's, using standard probabilistic updating procedures.

Consider first the problem of updating with objective infor­ mation. The standard way of doing this update is via condi­ tioning. For a distribution J.1- E I::J.x and an event B ~ X, define J.i-IB to be the distribution that assigns probability J.l-(w)/J.l-(B) to every w E B, and zero to all other states. For a set of distributions 1J x ~ I::J.x, define 1J xI B to be {J.i-IB: J.i-EVx}.

Proposition 5.3: Let B ~ X be an event. /f1J x and 1Jy cor­ respond under f, then Dx IB and Dy lf(B) also correspond under f.

What if we want to update on a constraint which is not objective? The standard extension of conditioning to this case is via cross-entropy [Kullback and Leibler, 1951].

Definition 5.4: The cross-entropy of J.l- 1 relative to f.l-, denoted C(J.l- 1 , f.l-), is defined as LwEW f.l- 1 (w) log(f.l-'(w)/ J.l-(w)). Fora distribution J.1- over X and a constraint B, let J.i-IB denote the set of distributions J.i- 1 satisfying B for which C(f.l- 1 , J.l-) is minimal. I

Intuitively, C(J.1- 1 ,J.l-) measures the "distance" from J.1- tot-"· The distribution J.l- 1 satisfying B for which C (J.l- 1 , J.1-) is minimal can be thought of as the "closest" distribution to J.1- that sat­ isfies B. If B denotes an objective constraint, then the unique distribution satisfying B for which C(J.l- 1 , J.l-) is minimal is the conditional distribution J.i-IB. That is why we have deliber­ ately used the same notation here as for conditioning. We also define Dx IB as we did for conditioning.

We can now apply a well-known result (see, e.g., [Sei­ denfeld, 1987]) to generalize Proposition 5.3 to the case of cross-entropy.

Theorem 5.5: Let B be an arbitrary constraint over flx. If Vx and Vy correspond under f, then Dx IE and Dy lf(B) also correspond under f.

As we now show, Theorem 5.5 gives us a way to "boot­ strap" invariance. We construct an inference procedure that uses cross-entropy starting from some set of prior probability distributions. Intuitively, these encode the user's prior beliefs about the domain. As information comes in, these distribu­ tions are updated using cross-entropy. If we design our priors so that certain invariances hold, Theorem 5.5 guarantees that these invariances continue to hold throughout the process.

Formally, a prior function P takes a space X and returns a set of probability distributions in flx. We now define an inference procedure fP as follows. We define I~ (KB) = {J.tiKB : J.l E P(X)}. Note that !~(true)= P(X), so that when we have no constraints at all, we use P(X) as the basis for our inference. Most of the standard inference procedures are of the form fP for some prior function P. It is fairly straightforward to verify, for example, that entailment is f---P for P(X) = flx. Standard Bayesian conditioning is of this form (at least for objective knowledge bases), where we take P(X) to be a single distribution for each space X. More interestingly, it is well-known [Kullback and Leibler, 1951] that maximum entropy is fP" where Pu (X) is the singleton set containing only the uniform prior on X.

So what can we say about the robustness of JP to represen­ tation shifts? By Theorem 5.5 and Proposition 5.2, we obtain the following corollary:

Corollary 5.6: JP is invariant under the embedding f from X toY iffP(X) and P(Y) correspond under f.

Thus, Corollary 5.6 tells us that if we want IP to be invariant under some set :F of embeddings, then we must ensure that our prior function has the right correspondence property.

This result sheds some light on the maximum entropy infer­ ence procedure. As we mentioned, f'vme is precisely the infer­ ence procedure based on the prior function P u. The corollary asserts that f'vme is invariant under f precisely when the uni­ form priors on X and Y correspond under f. This shows that maximum entropy's lack of representation independence is an immediate consequence of the identical problem for a uniform prior. Is there a class :F of embeddings under which maximum entropy is invariant? Clearly, the answer is yes. It is easy to see that any embedding that takes the elements of X to (disjoint) sets of equal cardinality has the correspondence property required by Corollary 5.6. It follows that maximum entropy is invariant under all such embeddings. In fact, the requirement that maximum entropy be invariant under a sub­ set of these embeddings is one of the axioms in a well-known axiomatic characterization of maximum-entropy [Shore and Johnson, 1980].

If we do not like the behavior of maximum entropy under representation shifts, Theorem 5.6 provides a solution. We should simply start out with a different prior function . Of course, if we want to maintain invariance under all represen­ tation shifts, we are forced to use the class of all priors, which gives us entailment as an inference procedure. If, however, we have prior knowledge as to which embeddings encode "rea­ sonable" representation shifts, we can often make do with a smaller class of priors, resulting in an inference procedure that is more prone to leap to conclusions. Given a class of

"reasonable" embeddings :F, we can often find a prior func­ tion P which is "closed" under each f E :F. That is, for each distribution J.l E P(X) and each embedding f E F from X toY, we make sure that there is a corresponding distribution v E P(Y), and vice versa. Therefore, we can guarantee that P has the appropriate structure using a process of closing off under each f in :F.

Of course, we can also execute this process in reverse. Say we want to support a certain reasoning pattern that re­ quires leaping to conclusions. The classical example of such a reasoning pattern is, of course, a default assumption of in­ dependence. What is the "most" representation independence that we can get without losing this reasoning pattern? As we now show, Theorem 5.6 gives us the answer.

An independence structure n over <1>* (our fixed infinite vocabulary) is a partition of the symbols in <1>* into a collection of disjoint sets or cells <1> 1, <1>2, .... A distribution J.l on W( <1>) respects the independence structure n if, for any formulas <p; E £(<!>; n <1>) and <pj E £(<1>j n <1>) with i # j, we have J.L(<p; 1\ <pj) = J.L(<p;)J.L(<pj). Thus, J.l makes the denotations of the symbols in different cells independent. Let pn ( <1>) be the class of all distributions J.l over W( <1>) that respect n. We can prove that f---P enforces minimal default independence for symbols in diff;rent cells. In fact, it satisfies a somewhat stronger property.

Theorem 5.7: Let '¥1 and '¥2 be disjoint vocabularies each of which is the union of cells in n. If KB 1 E _cpr ('¥ 1), 81 E £('¥!), KB2 E _cpr('¥2), {h E £('1'2), then KB1 1\ KB2 f'--Pn Pr( BdB2) = Pr( 81 ).

Theorem 3.12 shows that f---Pn cannot be invariant under all embeddings. Theorem 5.6 tells us that it is invariant under precisely those embeddings for which Pn is invariant. To characterize these embeddings, suppose that p is in one cell and q and r are in another. Since p and q are in different cells, we have true f---p Pr(plq) = Pr(p) . However, since q and r are in the same cell, we do not have true f---p Pr( r I q) = Pr( r). Hence, Pn is not invariant under an embedding f that maps p to r. Intuitively, the problem is that f is "crossing cell boundaries". If we restrict to embeddings f that do not cross cell boundaries, i.e., those that for any p E <l>; have f(p) E £(<!>;),then we avoid this problem.

Proposition 5.8: The inference procedure f'--Pn is invariant under any embedding f that is faithful and does not cross cell boundaries.

Theorem 5.6 allows us to define an inference procedure f---p that enforces minimal default independence (for formulas in different cells), and at the same time is invariant under a large and natural class of embeddings. Given our negative result in Theorem 3.12, this is the best that we could possibly hope for. In general, Theorem 5.6 allows us to understand the tradeoffs between inductive reasoning patterns and invariance under representation shifts.

6 Related Work

Given the importance of representation in reasoning, partic­ ularly inductive reasoning, and the fact that one of the main criticisms of maximum entropy has been its sensitivity to rep­ resentation shifts, it is surprising how little work there has been on the problem of representation dependence. Indeed, to the best of our knowledge, the only work on representa­ tion independence in the logical sense that we have consid­ ered here is that of Salmon. Salmon [Salmon, 1961] defined a criterion of linguistic invariance, which seems essentially equivalent to our notion of representation independence. He tried to use this criterion to defend one particular method of inductive inference but, as pointed out by Barker in the com­ mentary at the end of [Salmon, 1961], his preferred method does not satisfy his criterion either. Salmon then tried to find a modified inductive inference method that did satisfy his crite­ rion [Salmon, 1963], but it is not clear that it does; in any case, our results show that his modified method certainly cannot be representation independent in our sense.

Although statisticians have not considered representation independence in the sense we have defined it here, Bayesian statisticians have been very concerned with related issue of invariance under certain transformations of parameters. For example, we would expect that our beliefs about a person's height should be invariant under a transformation from feet to meters. Their hope is that once we specify the transfor­ mation under which we want a distribution to be invariant, the distribution will be uniquely determined [Jaynes, 1968; Kass and Wasserman, 1993]. In this case, the argument goes, the uniquely determined distribution is perforce the "right" one. This idea of picking a distribution using its invariance properties is in the same spirit as the approach we take in Sec­ tion 5. But unlike the standard Bayesian approach, we do not feel compelled to choose a unique distribution. This enables us to explore a wider spectrum of inference procedures.

Another line of research that is relevant to representation independence is the work on abstraction [Giunchiglia and Walsh, 1992; Nayak and Levy, 1994]. Although the goal of this work is again to make connections between two different ways of representing the same situation, there are significant differences in focus. In the work on abstraction, the two ways of representing the situation are not expected to be equivalent. Rather, one representation typically abstracts away irrelevant details that are present in the other. On the other hand, their treatment of the issues is in terms of deductive entailment, not in terms of general inference procedures. It would be interesting to combine these two lines of work.

7 Conclusions

This paper takes a first step towards understanding the is­ sue of representation dependence in probabilistic reasoning, by defining notions of invariance and representation indepen­ dence, showing that representation independence is incom­ patible with most types of inductive inference, and defining limited notions of invariance that might that allow a com­ promise between the desiderata of inductive reasoning and representation independence. Our focus here has been on in­ ference in probabilistic logic, but the notion of representation independence is just as important in many other contexts. Our definitions can clearly be extended to non-probabilistic logics. It is interesting to see in what circumstances our results also carry over. Are there any non-deductive logics that are repre­ sentation independent? We intend to examine this question in future work.