7.7 Reasoning about Independence

7.7 Reasoning about Independence

As was observed earlier, the language ^QU_n cannot express independence. A fortiori, neither can ^RL_n. What is the best way of extending the language to allow reasoning about independence? I discuss three possible approaches below. I focus on probabilistic independence, but my remarks apply to all other representations of likelihood as well.

One approach, which I mentioned earlier, is to extend linear likelihood formulas to polynomial likelihood formulas, which allow multiplication of terms as well as addition. Thus, a typical polynomial likelihood formula is a₁ℓ_i1(Φ₁)ℓ_i2(Φ₂)²−a₃ℓ_i3(Φ₃)>b.

Let ^QU, _n be the language that extends ^QU, _n by using polynomial likelihood formulas rather than just linear likelihood formulas. The fact that φ and ψ are independent (according to agent i) can be expressed in ^QU, _n as ℓ_i(Φ ∧ ψ) = ℓ_i(Φ) ℓ_i(ψ).

An advantage of using ^QU, _n to express independence is that it admits an elegant complete axiomatization with respect to ^meas_n. In fact, the axiomatization is just AX^prob_n, with one small change—Ineq is replaced by the following axiom:

Ineq⁺. All instances of valid formulas about polynomial inequalities.

Allowing polynomial inequalities rather than just linear inequalities in the language makes it necessary to reason about polynomial inequalities. Interestingly, all the necessary reasoning can be bundled up into Ineq⁺. The axioms for reasoning about probability are unaffected. Let AX^prob, _n be the result of replacing Ineq by Ineq⁺ in AX^prob_n.

Theorem 7.7.1

AX^prob, _n is a sound and complete axiomatization with respect to ^meas_n for the language ^QU, _n.

There is a price to be paid for using ^QU, _n though, as I hinted earlier: it seems to be harder to determine if formulas in this richer language are valid. There is another problem with using ^QU, _n as an approach for capturing reasoning about independence. It does not extend so readily to other notions of uncertainty. As I argued in Chapter 4, it is perhaps better to think of the independence of U and V being captured by the equation μ(U | V) = μ(U) and μ(V | U) = μ(V) rather than by the equation μ(U ∩ V) = μ(U) μ(V). It is the former definition that generalizes more directly to other approaches.

This approach can be captured directly by extending ^QU_n in a different way, by allowing conditional likelihood terms of the form ℓ_i(Φ | ψ) and linear combinations of such terms. Of course, in this extended language, the fact that φ and ψ are independent (according to agent i) can be expressed as (ℓ_i(Φ | ψ) = ℓ_i(Φ)) ∧ (ℓ_i(ψ | Φ) = ℓ_i(ψ)).

There is, however, a slight technical difficulty with this approach. Consider a probability structure M. What is the truth value of a formula such as ℓ_i(Φ | ψ) > b at a world w in a probability structure M if μ_{w, i}([[ψ]]_M) = 0? To some extent this problem can be dealt with by taking μ_{w, i} to be a conditional probability measure, as defined in Section 4.1. But even if μ_{w, i} is a conditional probability measure, there are still some difficulties if [[φ]]_M =∅ (or, more generally, if [[Φ]]_M∉ ′, i.e., if it does not make sense to condition on φ). Besides this technical problem, it is not clear how to axiomatize this extension of ^QU_n without allowing polynomial terms. In particular, it is not clear how to capture the fact that ℓ_i(Φ | ψ) ℓ_i(ψ) = ℓ_i(Φ ∧ ψ) without allowing expressions of the form ℓ_i(Φ | ψ) ℓ_i(ψ) in the language. On the other hand, if multiplicative terms are allowed, then the language ^QU, _n can express independence without having to deal with the technical problem of giving semantics to formulas with terms of the form ℓ_i(Φ | ψ) if μ([[ψ]]_M) = 0.

A third approach to reasoning about independence is just to add formulas directly to the language that talk about independence. That is, using the notation of Chapter 4, formulas of the form I(ψ₁, ψ₂ | Φ) or I^rv(ψ₁, ψ₂ | Φ) can be added to the language, with the obvious interpretation. When viewed as a random variable, a formula has only two possible values—true or false—so I^rv(ψ₁, ψ₂ | Φ) is equivalent to I(ψ¹, ψ² | Φ) ∧ I(ψ₁, ψ₂ | Φ). Of course, the notation can be extended as in Chapter 4 to allow sets of formulas as arguments of I^rv.

I and I_rv inherit all the properties of the corresponding operators on events and random variables, respectively, considered in Chapter 4. In addition, if the language contains both facilities for talking about independence (via I or I_rv) and for talking about probability in terms of ℓ, there will in general be some interaction between the two. For example, (ℓ_i(p) = 1/2) ∧ (ℓ_i(q) = 1/2) ∧ I(p, q | true) ⇒ ℓ_i(p ∧ q) = 1/4 is certainly valid. No work has been done to date on getting axioms for such a combined language.