Ignorant Influence Diagrams

1 Introduction

Bayesian Belief Networks (BBNs) [Pearl, 1988] are a well­ known formalism to reason under uncertainty and they have been successfully applied to a variety of problems in different domains. A BBN is a direct acyclic graph in which nodes represent stochastic variables and arcs rep­ resent conditional dependencies among variables. From a probabilistic point of view, they provide a straightfor­ ward way to represent independence assumptions among variables, thus making easy the representation and the acquisition of knowledge. BBNs are particularly appeal­ ing since they are based on a sound probabilistic seman­ tics and they easily extend into a complete decision the­ oretic formalism, called Influence Diagrams (IDs). IDs [Horvitz et al., 1988] provide a compact representation for decision problems and their sound probabilistic se­ mantics guarantees the normative character of their de­ cisions. IDs are an appealing complement to more tradi­ tional methods for representing decision problems, such as tables of joint probability distributions or decision trees, because they exploit the ability of BBNs to ex­ press conditional independence assumptions in graphical terms, thus dramatically reducing the amount of infor­ mation needed to specify a decision problem.

Nonetheless, a BBN still requires a fixed and poten­ tially very large amount of probabilistic information, that is not always available to the decision maker: the number of conditional probabilities needed to specify a conditional dependency grows exponentially with the number of its parent variables. Current propagation al­ gorithms require that all the conditionals probabilities defining a conditional dependency among variables have to be known, as well as all prior probabilities for the states of the root variables, before any reasoning process can start. Furthermore, these probability measures have to be assessed as point-valued probabilities, even when the decision maker is not completely sure about them. This requirement, called Credal Uniqueness [Stiling and Morrel, 1991], is one of the most controversial points of Bayesian probability and decision theory [Levi, 1980; Kyburg, 1983], and it is the reason why BBNs require such a large amount of probabilistic information: in or­ der to specify a unique probability distribution over the stochastic variables of a BBN, we need to know the con­ ditional probabilities relating it with all its parents in the network.

This limitation becomes even more apparent in the de­ velopment of an ID: when the decision maker is not able to specify a single probability, he is nonetheless forced to provide point-valued probability measures, and then to perform a costly and tiring analysis to assess the sen­ sitivity of the resulting decisions to all the possible com­ binations of his imprecise assessment.

To overcome this limitation, and maintain the ap­ pealing features of probabilistic soundness and graphi­ cal nature of BBNs, we have developed a class of BBNs, called Ignorant Belief Networks (IBNs) [Ramoni and Riva, 1994], able to relax the Credal Uniqueness assump­ tion and to reason on the basis of incomplete proba­ bilistic information. IBNs implement an inference pol­ icy, largely wished in the literature about probabilistic reasoning systems, called incremental refinement policy [Horvitz, 1989], able to improve the accuracy of the so­ lutions as a monotonically increasing function of the al­ located resources and the available information.

The aim of this paper is to extend IBNs into a complete decision theoretic formalism called Ignorant Influ­ ence Diagrams (liDs), and to show how liDs can be useful to model decision making when the information required by traditional IDs is not available. The reminder of this paper will briefly outline the theory and the properties of the IBNs. Then, it will describe the way in which an IBN can be extended into an liD and which decision proce­ dures are needed when the available information is not sufficient to specify point-valued probability measures. It will also outline a new method, provided by liDs, to assess the reliability of decisions without the costly sen­ sitivity analysis required by traditional IDs. A simple example will illustrate the properties of liDs and a brief comparison with some related works will be provided.

2 Ignorant Belief Networks

The representation and use of incomplete information is a long standing challenge for AI researchers. Dur­ ing the past decade, they have developed a class of reasoning systems, called Thuth Maintenance Systems (TMSs) [McAllester, 1990], which incrementally record justifications for beliefs and propagate Boolean truth values along chains of justifications. TMSs are indepen­ dent reasoning modules which incrementally maintain the beliefs for a general problem solver and enable it to reason on the basis of temporary assumptions and incomplete information. TMSs able to propagate proba­ bilistic rather than binaries truth-values are called Be­ lief Maintenance Systems (BMSs) [Falkenhainer, 1986; Laskey and Lehner, 1989]. IBNs are belief-maintained BBNs: they exploit a BMS based on probabilistic logic, and therefore called Logic-based BMS (LBMS) [Ramoni and Riva, 1993].

2.1 Belief Maintenance

A LBMS uses a standard propositional language £ defined by a set of atomic propositions S = { a1, a2, ... , an} and by the standard Boolean operators ·, V, /\ 1 :J, and =:. A literal l is an atomic proposition a; or its negation ·a;. An atomic proposition a; is a positive literal and the negation of an atomic proposition ·a; is a negative lit­ eral. A clause Cis a finite disjunction of literals V:= 1 l;. A Conjunctive Normal Form ( CNP) formula I is a finite conjunction of clauses /\!= 1 C;. Any legal formula of a propositional language can be converted into a CNP for­ mula.

The LBMS relaxes the Credal Uniqueness assumption by replacing the standard point-valued probability func­ tion p(f) with a convex set of these functions. The re­ sulting evaluation function P(f) of the language £ will define a real interval between two probability functions Pl (!) and P2 (!) such that

where a is a real number and 0 ~ a ~ 1. The interval assigned by the function P(f) to the formulas in £ is called the label of I and we will denote with P. (!) = 11" · and p· (!) = 1r· the lower and the upper bounds of the interval P(f) = [1r. 1r*], respectively. A label P(f) = [1r. 1r*] is satisfied for any subinterval of [1r. 1r*].

The LBMS uses a forward chained unit-resolution style algorithm called Epistemic Constraint Propagation (scP) to propagate labels over a network of propositional formulas. BCP can be regarded as an extension to inter­ vals of the Boolean Constraint Propagation (BcP) algo­ rithm [McAllester, 1990] used by the TMSs based on the propositional calculus. The intuition behind the BCP is simple and elegant. The algorithm starts converting any formula in CNP, that is, a set of clauses. Each clause acts as a constraint on the truth-values of the literals occur­ ring in it. To be satisfied, a clause must contain at least one literal labeled as true. A clause is violated when all the literals occurring in it are labeled as lal1e, thus producing a contradiction. When all literals but one in a clause are labeled as lal1e BCP forces the unlabeled literal to be true.

In order to extend the BCP from Boolean to probabilis­ tic truth-values, we derived, from the theory of proba­ bilistic entailment [Nilsson, 1986], a probabilistic inter­ pretation of disjunction able to define which constraints are imposed by a clause over the (probabilistic) truth­ values of the literals occurring in it [Ramoni and Riva, 1995].

The first constraint, imposed by a clause over the lit­ erals occurring in it states that the label of a literal l; in clause v:=lli is bounded by:

where

and the function lie is defined as

The second constraint states that the label of the literal It is bounded by:

where {It, ... , l,} is a set of literals, and {C1 , ··· , C2.-·} are the clauses built from {It, ... , l,} with all the possible combinations of the negated and unnegated literals in the set {l2, ... , l, }.

The propagation of these constraints is performed by a version of Waltz's propagation al~orithm [Waltz, 1975] extended to intervals [Davis, 1987j: each proposition is labeled with a set of possible values, and the constraints are used to restrict this set. This property, which is implicit in the form of the inequalities 2 and 3, implies a monotonic narrowing of the labels, thus ensuring the incrementality of BCP.

The most important feature of BCP is the ability to reason from any subset of the set of clauses representing a joint probability distribution, by bounding the probabil­ ity of the propositions within probability intervals, and incrementally narrowing these intervals as more informa­ tion becomes available. Furthermore, BCP is sound: it never excludes from its intervals any probability value that could be derived by standard probability theory from the available information. Even if incomplete in general, BCP is complete with respect to the clauses rep­ resenting a joint probability distribution. This means that, with respect to this subclass of the language, BCP returns the tightest entailed interval. The incomplete­ ness with respect to other clauses of the language is the result of a compromise between expressivity and effi­ ciency, since theoretical analysis and empirical results show that the BCP propagation runs to completion in linear time with respect to the number of clauses [Ra­ moni and Riva, 1995], thus making easy the estimation and the trading off of the computational effort.

2.2 Representation

IBNs are belief-maintained BBNS based on the LBMS. The IBN acts as a knowledge representation formalism ex­ pressing the assumptions of conditional independence in the domain of application and communicates the avail­ able conditional probabilities to the LBMS. These condi­ tional probabilities are transformed into clauses relating the propositions of the LBMS which represent states of the stochastic variables of the IBN. In this way, any computation is left to the LBMS and the IBN can exploit the incremental character ofBCP. The elements of a BBN can be easily translated into a LBMS network.

Nodes In a BBN, a node represents a stochastic vari­ able. A stochastic variable is a set of mutually exclu­ sive and exhaustive states. Therefore, the probability values assigned to the states in a variable have to sum to unit. In an IBN, when a variable is defined, each state is communicated to the LBMS as an atomic propo­ sition. Moreover, a set of clauses is installed to ensure that the states of the variable are mutually exclusive and exhaustive. For all propositions a1 1 ··· , an in the LBMS representing the states of the variable, the disjunction a1 V · · · V an and all the conjunctions --.(a, 1\ a;) (with i =/:- j) are asserted as true in the LBMS. When a proba­ bility value is assigned to a proposition a1 representing a state of the variable, the LBMS receives the conjunction P(at/\-.az/\ ... /\-.an)= P(at)·

Ares In a BBNs, arcs represent conditional dependen­ cies among nodes. A conditional dependency defines a dependency relation between a set of parent nodes and a child node. A conditional dependency is defined by the conditional probabilities P(a,la,., ... , a,) = [1r. 1r*], where a,., ... , a, is a combination of states of the stochas­ tic variables represented by the parent nodes of the de­ pendency and a1 is a state of stochastic variable repre­ sented by the child node. Conditional dependencies can be propagated both ways over an IBN, thus emulating the two main operations involved in the evaluation of a BBN: node removal and arc reversal.

2.3 Inference

There are two main operations involved in the evaluation of an 10: node removal and arc reversal. Node removal corresponds to propagating probability values along the direction of the arcs in the graph, while arc reversal cor­ responds to flowing backward the direction of the arcs and assessing the posterior probability of parent nodes in a dependency.

Node Removal In a BBN 1 node removal corresponds to marginalization. When the probability values of all states represented by the propositions a; ... a, is assigned, the two different clauses resulting from the application of the De Morgan's laws to (a; 1\a; ··. a,) and (-.a; I\ a; ... a,) are communicated to the LBMS al­ gorithm. P(a;l\a; ... a,) and P(-.a;l\a; .. . a,) are cal­ culated according to a version of the chain rule extended to intervals:

The resulting conjunctions are converted into clauses by the LBMS before propagating them through BCP.

Are Reversal From a probabilistic point of view, the capability of performing arc reversal in IBNs is provided by the well-known Bayes' Theorem:

where i rt {j, ... , 8 }. When provided with new evidence ~(a,), we can apply the chain rule to the conditional probability calculated by Formula 4 and p(a;) to obtain the conjunction: -

Since p(-.a;la; ... /\a,) = 1-p(a;la;/\ ... /\a,), we can also derive:

When converted into clausal form, these conjunctions turn out to be the same clauses that were generated dur­ ing marginalization. Therefore, arc reversal results in an updating of the probabilities of a set of already existing clauses. Extending this definition to intervals, the arc reversal formula for IBNs is obtained as follows:

It is worth noting that the resulting posterior probabil­ ity set is still convex, since it is the result of a linear mapping of the extreme values of a probability inter­ val, and BCP was proved to preserve convexity during propagations [Ramoni and Riva, 1993]. Furthermore, in IBNs, the inversion formula shares with the chain rule the appealing property of propagating only the available information, thus preserving the incremental refinement policy of BCP.

2.4 Properties

From the theory of TMSs, the LBMS inherits the concept of consumer [de Kleer, 1986]. A consumer is a forward­ chained procedure attached to a proposition, that is fired when the truth-value of the proposition is changed, that is, the probability interval associated with a state is narrowed. Using consumers, IBNs do not perform any computation themselves, but rather act as a high-level knowledge representation language, while the propaga­ tion of probabilities is performed by the LBMS.

There are some properties of the IBNs that will be crucial in the development of the liDs. First of all IBNs converge toward point valued probabilities, and when all the conditionals defining a joint probability distribution, they behave as standard BBNs, returning point-valued probabilities. Furthermore, an IBN will infer the tightest intervals from any subset of conditional probability in a conditional dependency, since the LBMS is compete for clauses representing joint probability distributions and the IBN simply minimizes and maximize the standard rules of node removal and arc reversal.

Finally, it is worth noting that the LBMS both performs and drives the propagation, since consumers are attached to the propositions of the LBMS and are fired according to the changes occurring in their labels. Therefore, the computational cost of a propagation grows linearly in space and time with respect to the number of condi­ tional probabilities, even if the number of conditional probabilities needed to specify a conditional dependency grows exponentially with the number of parent nodes in the dependency. However, the incremental character of inference policy implemented by the IBNs will allow the decision maker to trade execution time with precision of solutions, since an IBN will propagate only those con­ ditional probabilities explicitly assessed by the decision maker.

3 Influence Diagrams

IDs [Horvitz et al., 1988] are a natural extension ofBBNs. They allow the formulation of a decision problem into the sound and compact formalism of BBNs. In this section, we will illustrate how IBNs can be easily extended to a complete decision formalism, thus creating a new class of IDs called Ignorant Influence Diagrams (IIDs). liDs inherit from the IBNs the ability to reason on the basis of incomplete information and to incrementally refine the accuracy of their decisions as more information becomes available.

3.1 Representation

IDs are BBNs containing three different kinds of nodes: chance nodes (also called state nodes), decision nodes, and value nodes (also called preference nodes). These nodes are related by standard conditional dependencies. The resulting ID can be transformed into a BBN following the method proposed by Cooper [1988]. On this view, the decision problem can be solved by determining the instantiations of the decisions which maximize the ex­ pectations of the decision maker.

Chanee Nodes A chance node represents a state of the world. It is basically a standard stochastic variable. BBNs are usually defined as "influence diagrams contain­ ing just chance nodes" [Horvitz et al., 1988]. In Figure 1, chance nodes are depicted as oval nodes in the graph.

Deeision Nodes A decision node identifies a set of possible alternative actions available to the decision maker. In the IID of Figure 1, the decision node is de­ picted as a square node. A set of actions representing a possible solution for a decision problem is called strategy or policy.

Value Nodes Different strategies lead to different out­ comes. Value nodes represent preferences or utilities of the decision maker for alternative outcomes. A decision problem may be represented as the problem of finding the strategy which maximizes the preferences expressed by the decision maker over the possible outcomes of the problem. In Figure 1, the value node is depicted as a diamond.

3.2 Decision Criteria

A standard ID is solved by choosing the strategy with maximal expected utility ofits outcomes. In the example depicted in Figure 1, the expected utility of a strategy is the value assigned by the network to the value node. The optimal strategy ·· will be the strategy with the highest expected utility u(··)· As liDs propagate convex sets of probability distributions, they will also lead to convex sets of expected utilities for each strategy U(··)· We will denote with U.(··) and U*(··) the lower and upper bounds of the convex set of expected utilities for the strategy ··, respectively. There are several criteria to rank convex sets of expected utilities.

The most conservative criterion is called Stochastic Dominance [Kyburg, 1983] and dictates that a strategy ·· has to be preferred to a strategy ·; if and only if u. ( ·· ) > u· ( ·;) (i.e. the expected utility intervals do not overlap) . . This criterion is extremely safe, because it provides a decision if and only if there will be no chance that any additional information will change the ranking order among ·· and ·;· However, this criterion is often unable to discriminate in a variety of decision situations.

When the Stochastic Dominance criterion fails, we have to resort to a weaker condition of admissibility, able to discriminate among competing strategies when the expected utility intervals are not disjoint [Levi, 1980]. Pittarelli [1~88] proposes to adopt a generalised version of the well-know Hurwicz criterion. This criterion sug­ gests to rank the possible strategies according to a weight average of their minimum and maximum expected util­ ity, using a constant a , with 0 ::; a ::; 1. Therefore, the strategy ·· is preferred to the strategy ·; if and only if

The constant a, called Hurwicz value, can be thought as a boldness index representing the daring attitude of the decision maker. When a= 1, the Hurwicz criterion reduces to the well-known maximin criterion. The max­ imin criterion prescribes to select the strategy having the highest minimum expected utility. Hence, a strategy 6i is preferred to a strategy ·; if and only if U. ( ·i) > U. ( ·; ). This criterion reflects the behavior of a cautious decision maker, who wants to be sure that, even if an unfavor­ able state of the world occurs, there is a known minimum payoff below which he cannot fall.

When a = 0, the Hurwicz criterion collapses on the maximax criterion. The maximax criterion adopts the opposite point of view than the maximin criterion. It consider only the maximum expected utility of the strategies and select the strategy with the highest . Then a strategy ·i is preferred to a strategy ·; if and only if U*(··) > U*(·;). This criterion reflects the standpoint of a daring gabler who cares just about the maximum payoffs of his strategies and can afford to stand possible losses.

3.3 Sensitivity Analysis

Traditional decision theoretic formalisms require the assessment of point-valued probability measures, even when the decision maker is not completely confident about them. Since the decision maker cannot specify confidence intervals, he will have to perform a tiring and costly analysis of the sensitivity of the decisions to all the probability values he does not feel sure about. liDs reduce the cost of this procedure by solving the diagram just once and producing a sort of "simultaneous" mul­ tivariate sensitivity analysis. An advantage of this ap­ proach is that it provides a straightforward way to eval­ uate the sensitivity of decisions not only to prior prob­ abilities but also to conditional probabilities, which are usually difficult to modify and test using traditional sen­ sitivity analysis methods.

Furthermore, the adoption of the Hurwicz criterion to discriminate between competing strategies introduces a natural measure of the reliability of the decisions. When maximin and maximax criteria conflict, the Hur­ wicz value itself becomes a measure of reliability. We can analytically identify the decision threshold for the Hurwicz value in order to assess the sensitivity of the discrimination between the strategy ·· and the strategy ·; to the boldness attitude of the decision maker, using to the following formula:

Intuitively, this formula identifies for which Hurwicz value the decision maker will change his policy, and therefore the robustness of the decision reached so far. The lower is the decision threshold, the lower will be the chance that new information will change the preferred strategy, and therefore, the higher will be the quality of our decision. The value T will be an Hurwicz value (that is, 0 ::; .,. ::; 1) as long as one utility interval will be subset of the other, and therefore the maximin and the maximax criteria will conflict. When .,. < 0, both criteria will select the same strategy.

The optimality of these results is guaranteed by the ability of IBNs to return the tightest interval for any state from any subset of the conditional probabilities defining a conditional dependency and by the soundness of the method developed by Cooper [1988] to transform an ID into a BBN.

4 Example

In a standard ID, all the conditional probabilities that make up a conditional probability distribution are needed before any reasoning process can start. We will now show with an example how an liD is instead able to reason from incomplete conditional probability dis­ tributions. Figure 1 shows the liD used as an example. It represents the decision problem of taking a certain action in order to prevent a certain effect of a par­ ticular cause. The action has a foreseeable cost, and the problem consists in trading-off the value gained by prevention of the effect with the cost of the action.

The example is composed of two steps. In the first step, the system receives only the probability measures listed in the first column of Table 1, with the preference function over the outcomes defined as: v( [cost=yes] [effect=yes]) = 0, v( [cost=yes] [effect=no]) = 0.8, v( [cost=no] [effect=yes]) = 0.2, and v( [cost=no] [effect=no]) = 1. Figure 2 shows the graphical representation of the network gen­ erated in the first step of the example. The pop-up win­ dows over the nodes graphically report the probability interval associated to each one of their states. In each bar, the area between 0 and P. (a;) is black, the area be­ tween P"(a;) and 1 is white, and the area between P.(a;) and P"(a;) is gray. Thus, the width of the gray area is proportional to the ignorance about the probability.

The decision node reports its value in a strategy. The chances nodes report the probability values of each of their states for the same strategy. It is worth not­ ing that the conditional P( [effect=yes] I [cause=no] [act ion=no]), not reported in the first column of Ta­ ble 1, is actually not included in the definition of the first liD, and therefore its probability value is not even propagated. The value node value reports the expected utility intervals for the possible strategies [action=yes] and [action=no], namely: U( [action=yes]) [0.344 0.768] and U([action=no]) = [0.2767 0.7993].

It is apparent that the Stochastic Dominance crite­ rion is unable to select only one strategy, and remains undecided. The weaker Hurwicz criterion is able to pick up a unique decision. However, the solution can change according to the Hurwicz value. Using formula 5, we can estimate the robustness of the decision by calculat­ ing the decision threshold for the Hurwicz value. In our case, the decision threshold is T = 0.6825.

When all the probability measures required by a stan­ dard ID are specified, as in the second column of Table 1, the liD behaves as a standard ID in returning point­ valued probabilities, as shown in Figure 3. Since all the criteria adopted collapse on the maximum expected util­ ity criterion when they have to rank point-valued ex­ pected utilities, also the solution provided by the IID is identical to the one suggested by a standard ID.

5 Related Work

There are at least two line of research trying to relax the Credal Uniqueness assumption within a coherent Bayesian framework and to develop automated decision making systems able to reason on the basis of interval rather than point-valued probability functions.

The first line of research is based on the concept of probabilistic database, which generalizes the standard relational model by replacing the characteristic function of a relation with a finite probability distribution func­ tion. Using this concept, Pittarelli [1994] proposed a model able to represent probability intervals and pro­ vided methods for decision making based on it. The analogy between a probabilistic database and a table of joint probability distributions is apparent. Therefore, liDs improve the probabilistic database model as IDs im­ prove the traditional decision theoretic methods based on tables of joint probability distributions: liDs explic­ itly represent conditional independence assumptions in the domain of application, thus reducing the amount of probabilistic information needed to specify a decision problem.

Closer to the aim of liDs are the efforts addressed by Breeze and Fertig [1990] to develop Interval Influence Di· agrams. They describe procedures for node removal and arc reversal in IDs where lower bounds of probability in­ tervals are stored at each node in the ID. The appealing feature of this method is its effort to preserve both the probabilistic soundness and the graphical nature of stan­ dard IDs. Unfortunately, the probability bounds calcu­ lated by this method quickly degradate during the propa­ gation, thus resulting in the assignment of too wide prob­ ability intervals and jeopardizing the normative charac· ter of their decisions: an analog of the classical Dutch Book can be made against an agent malcing decisions on the basis of the probability distributions erroneously allowed by too wide probability intervals.

6 Conclusions

IDs are a powerful formalism to mechanize decision mak­ ing, and they have been successfully applied to a wide range of problems. However, they require a large amount of information that is not always available to the de­ cision maker. The acquisition of this large amount of information, either from human experts or from statis­ tical analyses of databases, usually represents one of the major challenges in the process of developing decision support systems based on IDs. This paper introduced a new class of IDs, called liDs, able to reason on the basis of incomplete information, and to incrementally refine the accuracy of their decisions as more information becomes available. However, when they are provided with com­ plete probabilistic information, liDs behave as standard IDs.

Therefore, liDs represent a net gain with respect to the traditional IDs, since they are able to explicitly represent the actual lack of information, without loosing any capa­ bility of the traditional IDs when the required informa­ tion is available. Furthermore, by relaxing the Credal Uniqueness assumption, liDs provide a new method to assess the reliability of the decisions by replacing the costly and tiring sensitivity analysis with a single an­ alytical measure. Finally, the monotonic, incremental character of the refinement process in the liDs provides a way to trade-off the amount of computational time and available information with the accuracy of the deci­ sions. This feature makes liDs a suitable formalism for real-time, resource-bounded decision tasks.

Acknowledgments

This research was supported in part by the AIM Pro­ gramme of the Commission of the European Communi­ ties (A2034). I would like to thank Alberto Riva, Greg Cooper, Carlo Berzuini and Riccardo Bellazzi for their helpful suggestions, and Mario Stefanelli for his contin­ uous support.