Foundations of Probabilistic Logic

ABSTRACT

We formalize a mathematical approach to probabilistic logic for zero-order logic and derive new inequalities that are necessary and sufficient for consistent probability assignments to propositions. We prove that a complete theory of probabilistic logic requires the a priori assignment of 21t-l probabilities for a system with k basic propositions. We also show that a ·proposal due to Cheeseman, namely, to regard measures of confidence in knowledge systems as expectations that are conditioned on unknown distributions, does not work in general. We demonstrate this by showing that several certainty measures proposed for expert systems are not consistent with the derived inequalities for probabilistic logiCs.

I INTRODUCTION: PROBABILISTIC LOGIC

A common practice in machine reasoning systems is the assignment of . a measure of plausibility to any statement. Several such assignments exist and have been the subject of experiments (Freedman and Shooman 198S; and Tong et al 1983). Some authors (Cheeseman 198S; Nilsson 1986; and Pearl 198S) have proposed probability theory, based on a classical Bayesian approach, for the basis of a formal theory of plausibility assignment for knowledge systems. (For surveys of other systems of assignment, see (Freedman 1986; Prade 198S; and Rescher 1964). Part of the problem of deriving consistent and complete probability assignments to statements concerns the formalization of the statistical dependencies between statements. Another problem concerns the definition of the correct sample space for statements.

Recently, (Nilsson 1986) has defined a sample space for propositions that results in a fundamental method of assignment, called probabilistic logic. Probabilistic logic is based on classical probability theory, with the standard operators for negation, conjunction, disjunction, and implication. Notation for these operators are given in

PROLOG notation as:

Let L be a set of propositions At A probability function on L (a probabilistic logic function) is a map

that is subject to two rules:

Rl. If A is a tautology, then p(A)·l.

R2. If not(A,B) is a tautology, then p(A;B) · p(A) + p(B).

A classical probability theory is a triple (S, 0, p) of a sample space S, a Boolean algebra of Borel sets 0, and a measure p defined for 0. Since we are concerned here with a discrete sample space, the probability theory is given by a "probability" P that is defined on all subsets of S that satisfies

H. Guggenheimer R.S. Freedman

Polytechnic University Route 110 Farmingdale, NY 1173S

• (i) P(S) · 1;
• (ii) P(lll) · 0, where Ill denotes the empty set;
• (iii) P(A UNION B) + P(A INTERSECTION B) · P(A) + P(B) for all A,B in S.

In order to justify the use of a probability theory in logic, one must show that conditions (1) and (2) imply that p has an interpretation as a classical probability on a · relevant sample space. The correct sample space recently defined by (Nilsson 1986) is given by the following:

Definition: The Nilsson Space N(L) of a set L of propositions is the . set or all consistent assignments or truth values to the elements of L.

For example, if L · {A, B, B:-A}, then N(L) · {xl, x2, x3, x4} where:

xl :· (T,T,T); x2 :· (T,F,F); x3 :· (F,T,T); x4 :· (F,F,T)

Truth value assignment is given by the truth function t, defined by:

t(A) · 1 if A is assigned truth T;

t(A) · 0 if A is assigned false F;

We note that in this example, the truth value of B:-A is uniquely determined by the truth values of A and B. Consequently, N(L) is in one-to-one correspondance with the Nilsson space for L'· {A, B). Here, L' is an example of a basic space associated with L.

Definition: A basic space associated with a set L or propositions is a maximal subset L' of L, such that the elements of L' can be assigned arbitrary truth values and then uniquely determine the truth values of all the other elements of L.

This implies that the cardinality of N(L) can be given as card(N(L)) · 2card(L'l.

Consequently, all basic spaces derived from a given L have the same cardinality.

We note that in the above example, neither {A, B:-A) or {B, B:-A) are basic sets, since in both cases, not all truth assignments for {A, B, B:-A) are possible: (F,F) is excluded in the first case, and (T,F) is excluded in the second case. Moreover, the value of the third proposition cannot be determined: (F,T) does not determine t(B) in the first case, and (T,T) does not determine t(A) in the second case. This implies that not every set of propositions admits a basic space. This leads to the following:

Definition: A set of propositions L is well-formed if has a basic space.

Given a proposition A in L, the indicator function for A, IA(x), is the function from· N(L) to {0,1) defined by:

IA(x) is the value of t(A) in the assignment x.

In our above example,

Definition: A Nilsson probability distribution is a classical probability defined on N(L).

Definition: The induced probability of a proposition A,p(A) is:

where E is the expectation of lA in the Nilsson probability distribution.

ll INEQUALITIES FOR PROBABILISTIC LOGIC

Properties of the indicator function are:

These properties are also seen in the induced probabilities:

Definition: Let L' be a basic set of a well-formed set L of propositions. The full space LA is the set of all, conjunctions of distinct elements of L'.

Any probability assignment on LA must satisfy a set of inequalities. Given the two tautologies A;not(A) and not(A,npt(A)) we have

Since A·(A,B);(A,not(B)) and (A,B),(A,not(B)) is the negation of a tautology,

By an inductive argument, we have the following inequality constraint For k · I .. card(L'):

This proves the theorem:

Theorem I: Any probability assignment on a well-formed set L which satisfies the rules RI and R2, must also satisfy the inequality constraint C 1.

ill NECESSARY AND SUFFICIENT CONDITIONS FOR PROBABILISTIC LOGIC

Our main theorem is:

Theorem 2: A probability assignment N(LA) on L'' (that is derived from a probability assignment of a well-formed set L) is consistent with rules RI and R2, if and only if it is the probability induced by a uniquely defined Nilsson probability distribution.

Our proof is based on classical linear algebraic and geometric methods, see (Guggenheimer I977).

The condition in Theorem 2 is necessary since Cl is implied by PI-P3. For sufficiency, we have to show that given probabilities for elements in LA (all conjunctives), and a set of indicator functions, there exists a unique induced Nilsson probability distribution.

Let the elements of LA be indexed from I to N·card(LA). We define the vector r to be the vector of all probabilities assigned to these elements, augmented by a "I". In other words,

(where T denote~ vector transpose). Since N· 2card(L'l-I, r is a vector in 2card(L) dimensional space. Let x be the vector of the (unknown) Nilsson distribution (in the same space), and let H be the matrix ·whose values are the values of the indicator function

where i denotes the index associated with the i-th element in LA, and j denotes the index of the j-th element in N(LA). From the definition of induced Nilsson probabilility (and expectation), the matrix-vector product r - H x holds.

For example, if

L · L' · LA · {A,B}, and N(L) · {xi, x2, x3, x4) - {(T,T), (T,F), (F,T), (F,F)} then we have

The rqws of H corresponding to Ail· Ai2····· Aik contain 2card(L'J-k ones; all other entries are zero. The last row has all ones. In our above example, this is seen when we evaluate the indicator functions, so

The zero indicator function (all propositions assigned F) is the column (0, 0, ... O,I)T. The last row in H implies that x1 + x2 + ... + XN · }.

The matrix H can be reduced to the identity matrix by elementary matrix operations (Gaussian elimination) starting with the row corresponding to

This row is zero except for one "I". H is not singular and consequently, x - H- 1 r, uniquely.

We now show that 0 S xk s I, for vector x. All rows of H (except the last ,row of H that consists of all l's) can be considered to represent vectors in the faces of the unit cube (in card(L')-1 dimensional space) in the hyperplane xcard(L')·l. Since the coordinates of these rows consist of only 0 antl I, and the rows (considered as vectors) are linearly independent, we can obtain all vertices of the unit cube by any linear combination of vectors. Consequently, given any Nilsson probability distribution n, the set of all matrix-vector products (H n) is the convex hull of the all vertices of the unit cube. This implies that the vector r is also in the convex hull of the unit cube. Since x-H-1r is unique, x must also be a Nilsson probability distribution. (QED)

IV APPLICATIONS

We have shown that a complete theory of probabilistic logic based on Nilsson distributions requires the a priori assignment of 2t-1 probabilities for a system with k basic propositions. In practice, such an assignment is possible only for small values of k. However, we can always rely on the following:

Corrollary: All inequalities between probabilities defined on a well-formed Boolean logical system are consequences of Cl.

Some examples of derived inequalities are Nilssons's inequality (Dl).

• D3. max(p(not(A)),p(B))sp(B:-A)smin(l,p(not(A)) + p(B))

Cheeseman (I) has proposed to regard measures of confidence attached to statements in expert systems ("uncertainty calculi") as expectations that are conditional upon unknown probability distributions. We show that this approach does not work in general by reviewing some uncertainty calculi that . have been proposed and investigated in (Freedman J9g6; Freedman and Shooman 1985; Prade 1985; and Tong et al 1983).

The system of Lukasiewicz-Goguen postulates the following measure of confidence c:

LG2. c(B:-A) · min (1, c(B)Ic(A))

Rule LGI is consistent with Cl. In order to check if Rule LG2 is also consistent with probabilistic logic, we consider it ·as a measure of confidence for modus ponens. According to Cheeseman's approach, we interpret LG2 in the following way:

where n is some unknown probability distribution. However, from the definition of conditional probability and constraint CI,

LG2 then implies p(B I n) · p(A,B I n) and, by LGI, p(A I n) · I, which is not valid for arbitrary probability assignments. Consequently, LG2 with LG I is not consistent with probabilistic logic.

The system of Dienes is based on

DUI. c(A,B) · c(A)·c(B)

DU2. c(B:-A) · max (I - c(A), c(B))

Rule DUI implies that for any probabilistic interpretation

If this is applied to a Nilsson probability, DU2 shows that

Nilssons inequality Dl shows that p(B:-A) :!: p(B); therefore, DU2 is valid only if p(B) > I - p(A). Consequently, DU2 is not an assignment (compatible with any interpretation as an expectation) that is consistent with probabilistic logic.

The Zadeh-Godel assignment is

Zl. c(A,B) · min(c(A), c(B))

Z2. c(B:-A) · min (1, c(B)Ic(A))

Z3. c(not(A)) · I - c(A)

This assignment is compatible with the interpretation

where the maximum ranges over all probability vectors n. This assignment, while consistent, seems overly optimistic. This assignment is also an example of a Dempster upper probability (Dempster 1967).

V CONCLUSIONS AND FUTURE WORK

Our theory pb~ces probabilistic logic on a firm mathematical foundation. On this basis, we already have obtained limit theorems for Dempster theory that greatly reduce computation in Demster-Shafer theory. We are now developing probabilistic limit theore!Jls for Bayesian, fuzzy, and rule based reasoning systems.