A Method of Computing Generalized Bayesian Probability Values for Expert Systems

Abstract

This paper presents a new method for calculating the condi t ional probability of any multi-valued predicate given par­ ticular information about the individual case. This calcula­ tion is based on the principle of Maximum Entropy (ME), sometimes called the principle of least information, and gives the most unbiased probability estimate given the available evidence. Previous methods for computing maximum entropy values shows that they are either very restrictive in the probabil­ istic information (constraints) they can use or combinatorially explosive. The computational complexity of the new procedure depends on the inter-connectedness of the constraints, but in practical cases it is small. In addition, the maximum entropy method can give a measure of how accurately a calculated con· ditional probability is known.

§l Introduction

Recently computer-based expert systems have been de­ veloped that store probabilistic knowledge obtained from ex­ perts and use this knowledge to make probabilistic predictions in specific cases. Similarly, analysis of data, such as question­ naire results, can reveal dependencies between the variables that can also be used to make probabilistic predictions. The essen­ tial problem in such systems is how to represent all known de­ pendencies and relationships, and how to use such information to make specific predictions. For example, knowledge of inter­ relationships between factors such as age, sex, diet, cancer risk etc. should allow the prediction of say an individual's cancer risk, given information on the individual. However because of possible interactions between the factors, it is not sufficient to combine the effects of each factor separately.

The major problem faced by all such probabilistic in­ ference systems is that the known constraints usually under­ constrain the probability space of the domain. For example, if the space consists of 20 predicates, then 2 20 - 1 joint probabil­ ity constraints are needed to fully specify all the probabilities. When a space is under- constrained, any desired probability usually has a range of possible values. The problem is to find a unique probability value within the allowed range that is the best estimate of the true probability, given the available infor­ mation, and to determine how reliable this estimate is. Such an estimate is given by the method of maximum entropy (ME), sometimes called the method of least information. This method gives a probability value that is the least commitment value, subject to the constraints. To choose any other value has been shown by Shore and Johnson (1980) to be inconsistent, because

A Method of Computing Generalized Bayesian Probability Values For Expert Systems

Peter Cheeseman

SRI International, 333 Ravenswood Road Menlo Park, California 94025

any other choice would imply more information than was given in the problem.

This paper focuses on a type of expert system in which all the probability constraints are in the form of conditional probabilities or joint probabilities (sometimes called marginal probabilities because they occur in the margins of contingency tables). Such probability constraints may have come from an expert or from an analysis of data that has shown that particular subsets of factors are significantly correlated. The problem of making probabilistic predictions in under-constrained probabil­ ity spaces is of sufficient importance that many solutions have been tried. One method is to acknowledge that the desired probabilities are under constrained and return the range of pos­ sible values consistent with the known constraints (rather than a point value). Such an approach is implicit in the method proposed by Shafer (1979).

Another method is to make the strong assumption of condi t ional independence when combining different evidence. This is the assumption behind PROSPECTOR (Duda fl a/. , 1976) and Dependence Trees (Chow and Liu 1968) and used most recently by Pearl (1982). Use of the conditional indepen­ dence assumption with given conditional probabilities is usually sufficient to constrain the desired probabilities to a unique value. However , t his assumption is not always satisfied by actual data and can lead to inconsistent and over-constrained probability values, as pointed out by Konolige (1979).

The main purpose of this paper is to introduce a new method for computing the maximum entropy probability of a predicate of interest, given specific evidence about related predi­ cates, and subject to any linear probability constraints. This method avoids the combinatorial explosion inherent in previous methods wi t hout imposing strong limitations on the constraints that can be used, and it is therefore useful for computer-based expert systems.

§2 The Maximum Entropy Method

The method of maximum entropy was first applied by Jaynes to the statistical mechanics problem of predicting the most likely state of a system given the physical constraints (e.g. conservation of energy). In Jaynes (1968), the maximum entropy method was used to provide prior probabilities for a Bayesian analysis. Lewis (1959) applied the method of least information (an equivalent method) to the problem of finding the best approximation to a given probability distribution based on knowledge of some of the joint probabilities (i.e., constraints on the possible distributions).

Ireland and Kullback (1968) applied the minimum discrimina­ tion information measure (yet another method equivalent to maximum entropy) to find the closest approximating probability distribution consistent with the known marginals in contingency table analysis. Konolige (1979) applied the least information method to expert systems, and this analysis has been extended by Lemmar and Barth (1982).

The mathematical framework used in this paper is defined below. Although the definitions are given for a space of four parameterized predicates, the framework applies to any number of predicates. The predicates are A, B,C, and D where:

and Pijkl is the probability that A has value i, B has value j , C has value k , and D has value /.

F'or example, A might be the predicate "soil-type" where A1 has the value "clay," A2 is "silt" and so on. Each value (category) of a predicate is assumed to be mutually exclusive and exhaustive of t he other categories . Any predicate that is not currently exhaustive can be made so by adding an extra category "other" for anything that does not fit the existing categories. In terms of these predicates, the entropy function (H) is defined below:

H is a measure of the uncertainty inherent in the component probabilities. F'or example, if one of the Pijkl values is 1 (and so all the r<'st are zero), then His zero-i .e., there is no uncertainty, as expected. Conversely, H can be shown to be a maximum when all t he Pijkl values are equal (if there are no constraints)­ t his represents a state of maximum uncertainty.

Because the Pijkl values are probabilities, they must obey t he following constraint:

In addition, any subset of the following constraints may be asserted:

joints; such as

conditional probabilities, such as:

and probability assignment to arbitrary logical functions, e.g.

These constraints are given explicitly because their values differ significantly from their expected ME value. Such significant constraints could be specified by experts or found by a program that examines data looking for significant combina­ tions. The main reason for calculating ME probability values on the basis of the known constraints is to be able to find any probability value without having to store the entire probabil­ ity space. Only linear constraints involving equalities have been given above, but the ME method can be extended to include non­ linear constraints as well. Note that (2), for example, is itself a set of constraints- one for each value of i given. Also it is as­ sumed here that if either the numerator or the denominator of a conditional probability constraint is given separately (as a joint probability constraint), then the conditional probability con­ straint is replaced by the equivalent joint probability (marginal) constraints. The last constraint indicates that a probability as­ signment to any logical formula is equivalent to a probability assignment to a subset of the total probability space, and so forms a simple linear constraint.

The principle of maximum entropy requires that a unique set of values for Pijkl be found that satisfies the given constraints and at the same time maximizes the value of H given by (1). A method for calculating this ME distribution is discussed in the following section. The reasons for accepting ME probability values as the best estimate of the true probability ane discussed in Jaynes (1979) and Lewis (1959), and may be summarized as follows . In expert system applications, when all the significant constraints (e.g., marginals and conditionals) have been found, all the information about the domain is contained in these con­ straints. Any ME probability value calculated with these con­ straints has distributed our uncertainty (H) as evenly as pos­ sible over the underlying probability space in a way consistent with the constraints. Returning any non-ME value implies that extra information is being assumed because H is no longer a max1mum.

The shape of a particular H distribution around the ME value indicates how well the particular calculated probability is constrained by the available information. A strongly peaked curve indicates that the value is highly localized around the ME value, whereas a relatively flat curve indicates that very little information about the cal~ulated probability is available­ i.e., it is essentially unknown. The difference between H for an assumed probability and H maximum (which occurs for the ME probability value) gives the amount of information assumed by choosing a non-ME probability value.

§3 A New Method of Calculating Maximum Entropy Distributions

The first use of maximum entropy (least information) for estimating probability distributions in computer science is due to Lewis ( 1959). He showed that if the given probabilities are conditionally independent then the underlying probability space can be represented by simple product formulas and that this is the maximum entropy distribution. This product form is the basis of Dependence Trees (Chow and Liu 1968) and the tree based Bayesian update method of Pearl (1982). An iterative techinique for computing the ME distribution given some of the joint probabilities without requiring conditional independence was developed by Brown (1959). This method was extended by Ku and Kullback (1969), but both authors put strong restric­ tions on the constrints that must be given, and their method combinatorially explodes if the space of predicates is large. The new method of computing ME distributions presented in this section avoids these difficulties.

The problem of optimizing a continuous function subject to constraints is a well-known one in applied mathematics and a general solution is the method of Lagrange multipliers. The specific problem of maximizing the entropy function (1) sub­ ject to constraints was first applied to the domain of statistical mechanics , and specifically to joint (marginal) constraints by Gokhale and Kullback (1978). This section derives the neces­ sary formul ae in a form suitable for efficient computation.

The first step is to form a new entropy function as defined below:

The next step is to equate the derivative of (5) (with respect to each variable) to zero, giving:

Equation (7) gives the ME distribution in terms of the >.s, so if t he values of all >.s can be found, the ME space is known implicitly. Note that equation (6) is the so-called loglinear form, but here this form is a direct consequence of the maximization of H rather than an ad hoc assumption. From (5) it is clear that there is only one ). per constraint and that these are the only unknowns. If equation (7) is substituted into (8-9) etc., (i.e., into each of the given constraints), then the resulting a set of simultaneous equations can be solved for the >.s. It is more convenient first to apply the following transformations:

i.e., the basic distribution P;jkl is given implicitly as a product of as . Equation ( 10) is the key to the new ME calculation method, as it implicitly gives the underlying probability space in terms of a product of parameters (the as), and there are only as many as as there are constraints. Note that for any particular P;jkl, only those as with the corresponding indices appear in the product. With t hese substitutions, equation (8) becomes:

and (9) becomes:

and so on (one equation for each constraint).

This set of simultaneous equations can be solved by any standard numerical techniques. However, in practice it is more common to need to update an existing solution by adding a new constraint. Such an update introduces a new corresponding (nonunity) o:, and causes adjustments to some of the existing o:s. Even when a set· of constraints is to be added, they can be intro­ duced sequentially, thus an update method is always sufficient to compute the o:s. A suitable update method is to assume ini­ tially that all the o:s have their old value, then calculate a value for the new or from the new constraint equation. This new value is inserted into each of existing constraint equations in turn, and revised o: values are calculated for the o: corresponding to each constraint. This process is repeated until all the a values have converged on their new values. Current investigations are trying to determine which ors change during update, the convergence of the method, and its computational cost.

§4 Probabilistic Inference

The previous section describes a method for representing (implicitly) the underlying ME probability distribution. This section describes how to use such a representation to calculate the conditional probability of any desired predicate, given in­ formation about a specific case. Such a computation requires summi ng over the probability space without creating a com­ binatorial explosion, as shown below.

Consider a hypothetical example with predicates A ; ,Dj.C k, Dt and Em, where each A; for example, could repre­ sent different age categories. If prior probabilities (constraints) are given for some of the predicate values and prior joint and conditional probabili t ies for combinations of values of different predicates, t hen the corresponding a values can be computed as explai ned in the previous section. The resulting probability space for a part icul ar combination of given prior probabilities might be:

If t he prior probabili ty of say a particular A; is required (i.e., it is not one of t he given priors) then the value is given by:

Here, the I; has been recursively decomposed into its com­ ponent part ial sums allowing each partial sum to be computed as soon as possible and the resulting matrix then becoming a term in the next outer-most I; . In the above example, this summat ion method reduces the cost of evaluating Ljklm from O(.J *K *L *M) (where J , .. ,M are the ranges of j , .. , m respectively) to O(J*L*M) - i.e., the cost of evaluating the innermost I; . Note that a different order of decomposition can produce higher costs -- i.e., the cost of I; evaluation is dependent on the evalua­ tion order , and is a minimum when sum of the sizes of the inter­ medi ate matrices is a minimum. When there are a large number of predicates. the total computational cost of evaluating a I: is usually dominated by the largest intermediate matrix, whose size is partly dependent on the degree of interconnectedness of t he predicat c being summed over and the order of evaluation. The above summat ion procedure is also useful in updating the previous as when given new prior probabilities. In the above, ao is a normali zation constant that can be determined, once all values of P(A;) have been evaluated, from the requirement that L ; r( ,1;) = I. This normalization makes prior evaluation or a0 unnecessary.

To find t he conditional probability of a predicate (or joint condi t ional probability or a set or predicates), all that is needed is to drop t.hose predicates whose values are given from the total I; . For example, to find the conditional probability of A; given t hat D2 and £ 3 are true, the correct formula is:

where j3 is a normalization constant. Note that the more evidence there is concerning a particular case, the smaller the resul ting I;. Also, the conditional probability evaluation proce­ dure is nondirectional because, unlike other expert systems, this procedure allows the conditional probability or any predicate to be found for any combination of evidence. That is, it has no spec ially designated evidence and hypothesis predicates.

The above probability evaluation method can be extented to include the case where the evidence in a particular case is in the form of a probability distribution over the values of a predicate that is different from the prior distribution, rather than being informed that a particular value is true. In this case, it is necessary to compute new a s t hat correspond to the given distribution and use these new as in place of the prior corresponding as in probability evaluations such as those above. For instance, if a new distribution is given for P(A;) , then the new as are given by:

Note that t he revised a values used in the above method are just multiplicati ve fact.ors whose value is identical to the correction factors of Lemmar and Barth (1982), and so the methods are equi valent in this case. The major difference is that here the probability space is represented implicitly by the as, and the corresponding summation procedure will work even when the space cannot be part itioned.

The above conditional probability evaluation procedure (a type of expert system inference engine) has been implemented in LISP and has been tested on many well known ME examples. In ME condi t ional probability calculations when given specific evidence, it bas been found that only short strong chains of prior joint or condit ional probabilities can significantly change the probabili ty of a predicate of interest from its prior value.

When a point probability value is computed by the proposed method, it is useful to also estimate its accuracy as well. There arc two sources of uncertainty in a computed ME value. One is t he possibility that the known constraints used are not t he on ly ones operating in the domain. This type of uncertainty is hard to quantify and depends on the methods used to find t he known constraints. If a constraint search is sys­ tematic (over t he known data), then we can be confident that we know all the dependencies that can contribute to a specific ME value. If a constraint search is ad hoc, it is always possible that a major contribut ing factor has been overlooked. If any important factors are missing, the calculated ME probability values will differ significantly from the observed values. If such devi at ions are found, it indicates that factors are missing, and an analysis of t. he deviations often gives a clue to these missing factors.

The other source of uncertainty is the accuracy with which the constraints are known. This accuracy depends on the size of the sample from which the constraints were extracted or the accuracy of the expert's est imates. This uncertainty is also hard to quantify, but it provides a lower limit on the accuracy of any calculated value. In the analysis given here, the constraints were assumed to be known with complete accuracy.

§5 Summary

This paper presents a new method of computing maxi­ mum entropy distributions and shows how to use these distribu­ tions and some specific evidence to calculate the conditional probability of a predicate of interest. Previous methods of com­ puting maximum entropy distributions are either too restrictive in the constraints allowed, or too computationally costly in non­ trivial cases. The new method avoids both these difficulties. Justifications for preferring maximum entropy values are given, as are ways of estimating their certainty.

Further research is necessary to further improve the efficiency of this method, particularly by automatically finding the optimal L evaluation order and discovery of approxima­ tions that would allow the exclusion from the summation of any predicates that could not significantly effect the final result. Such improvements should increase the usefulness of this ME computation technique as an expert system inference engine.