We introduce and analyze the pro blem of the compilation of decision models from a. decision-theoretic perspective. The techniques described allow us to evaluate various configurations of compiled knowledge given the nature of evidential relationships in a. domain, the utilities associated with alternative actions, the costs of run-time delays, and the costs of memory. We describe procedures for selecting a subset of the total observations available to be incorporated into a. compiled situation-action mapping, in the context of a binary decision with conditional independence of evidence. The methods allow us to incrementally select the best pieces of evidence to add to the set of compiled knowledge in an engineering setting. After presenting several approaches to compilation, we exercise one of the methods to provide insight into the relationship between the distribution over weights of evidence and the preferred degree of compilation. There has been growing interest in reducing complex deliberation in computer-based reasoners by devel oping decision-making techniques that rely on precomputed or compiled responses. In particular, recent reactive planning research has centered on the replacement of unwieldy solution mechanisms and detailed representations of knowledge with compiled strategies that enable agents to respond, in reflex fashion, to relatively simple perceptual inputs [1, 3] . It has been hoped that, for many contexts, explicit representations and deliberation will not be necessary for sufficient performance. To date, most of the work on compilation has been done in the absence of theoretical foundations of decision making under uncertainty. The goal has been to create reasoners with satisfi cing behavior. However, there has been growing interest in the optimal design of problem solvers and solution methodologies through the application of normative principles [8] . In this paper, we describe methods for the efficient representation and indexing of precomputed actions from a perspective of bounded optimality. Bounded-optimal systems perform ideally in some context or set of contexts under expected constraints in reasoning resources, such as  in time and memory [9] . We define optimality in the context of a decision-theoretic analysis of the costs and benefits of alternative hardware configurations and strategies for determining the best action. As viewed from the perspective of decision analysis, the compilation techniques to date [14, 1, 3, 11] typically have been suboptimal as investigators have relied on ad hoc models. Recent discussions on compilation, from the decision-theoretic perspective, have explored the derivation and consistency of compiled situation-action rules from underlying normative decision models [2] and the relationship of heuristics to decision-theoretic models [12] . It has been suggested that decision-theoretic approaches to the compilation of action, and the integration of compiled and computed approaches, may be useful in the development of tractable normative reasoning systems [9] . Indeed, recent work on the speed up of probabilistic inference through caching probabilistic results has been promising [7] . The development of elegant and theoretically sound techniques for compiling useful patterns of behavior undoubtedly will help enhance our understanding of the production of inexpensive, fast-acting, and well-characterized computa tional agents from more complex, explicit models of problem solving. Formal analyses can enable us to probe mathematically the relationships among parameters of problem solvers and domains, allowing us to glean new insights about compilation. Such insights may evade us in the context of less rigorous analyses. We address the reactive-planning problem from a decision-theoretic perspective. Our analysis centers on the application of knowledge about (1) the nature of evidential relationships in a domain, (2) the utilities associated with alternative actions, (3) the costs of run-time delay, and ( 4) the costs of memory. Our model provides intuition about the nature of ideal compilation strategies as a function of these parameters. The approach is similar in spirit to recent work on the control of probabilistic inference that applies knowledge about inference progress and future belief distributions to reasoning about the expected value of computation [10] . In this work, we analyze several approaches to compilation and explore the effects that different ass umptions about the distribution of evidence can be expected to have on the optimal configuration of compiled knowledge. A simple model for diagnosis is represented by the influence diagram pictured in Figure 1 . In this model, the utility of a situation, represented by the diamond-shaped node, labeled U, depends on (1) whether a particular hypothesis H is true or false, and (2) whether an action D is taken or not. We cannot observe H directly; rather, we are forced to do inference about the relative likelihood of H by observing pieces of evidence E �, E 2, ... , En· Thus, we seek to make a decision about a best action in the general case where we have incomplete information about the world. We shall simplify our an alysis by considering the case where D, H, and the Ei's are binary-valued variables (i.e., are true or false). To simplify our model further, we shall assume that all evidence is conditionally independent, given H or ..., H. In Section 5, we examine how these ass umptions can be relaxed. Finally, for definiteness , we ass ume that it is appropriate to take action D (as opposed to ..., D) if H is true. Using the ass umption of conditional independence of evidence, given the hypothesis and its negation, we can calculate the posterior probability of the hypothesis by multiplying together all of the likelihood ratios, P�JL'W), with the prior odds, P1L'W). Because D and H are binary, we can simplify our reasoning about whether we should take action D by calculating a threshold probability, p •, for the decision. This threshold probability is defined as the 163 Figure 1 : An influence-diagram representation of the diagnosis problem. The utility (diamond node, U) depends on a hypothesis (circular node, H) and a decision (square node, D). All evidence is available at the time the decision is made. probability H at which we are indifferent between acting and not acting. That is, we define p * as the point where acting and not acting have equal utility, or -p The weight of evidence, w;, is defined as the log of the likelihood ratio, In.\;. Mapping likelihood ratios into weights of evidence allows us to update belief in a probability through the addition of the weights of evidence. (See [4) for a discussion of the use of weights of evidence in the analysis of belief-updating schemes in formalisms for managing uncertainty in artificial intelligence.) We can rewrite the threshold-probability condition in terms of the log-likelihood ratio where w1 =In A;. It is better to act if and only if In this expression, w• is the threshold sum of weights of evidence for the decision problem. We will use this formulation of diagnostic decision making, in conjunction with the assumption that all evidence is conditionally independent, to analyze the tradeoffs associated with computation versus compilation. 3 Given a simple decision problem defined within the model of diagnosis and analytic framework described in Section 2, two fundamental design alternatives are: 1. Compute. Endow our computational decision maker with the ability to perform probabilistic inference in real-time, and commit to a decision that maximizes expected utility. That is, given a vector of information about the truth status of all of the relevant evidence, we compute m we require a memory cache of a size that grows exponentially with the number of pieces of evidence considered (an n-dimensional array). We wish to compare the relative costs and benefits of these two alternatives. To do so, we determine the net inferential value (NIV) of each alternative. The net inferential value of an alternative is the expected net present value of that alternative over the entire lifetime of its use. In this paper, we decompose this value into three components. The first component is the expected value of the recommendations provided by each method. In the general case, the compilation method will ignore some av ailable information. Thus, the quality of its recommendations typically will be lower than those derived from computing. The second component is the memory requirements of computation and compilation. Finally, we must consider the cost of processing time, based in delayed response, when a case presents itself. This cost may be depend on whether H is true (e.g., suppose H is the hypothesis that a patient is having a heart attack). Let EV compute denote the expected value of a system committed to the compute policy for a single episode. Also, let PC� mp uteand PC,;;, "% pu tedenote the processing costs for computation given H is true and  where r is a factor that converts the expected value of each policy on a single problem instance to a summary (present) value for a series of problem instances over the life of the system. (A discussion of bounded optimality and related issues on the value of a reasoning system over a lifetime and over a specific
In the realm of action under uncertainty, Heckerman, et al. investigated methods for the optimal compilation of actions given a finite quantity of memory REF .
The Compilation of Decision Models
ArXiv
ArXiv
Computer Science