文档介绍：Probability Bounds for Goal Directed Queries in works Michael V. Mannino Graduate School of Business Administration, Campus Box 165, . Box 173364 University of Colorado at Denver, Denver, CO 80217-3364 ******@ S. Mookerjee Department of Management Science, Box 353200 University of Washington, Seattle, WA 98195-3200 ******@ derive bounds on the probability of a goal node given a set of acquired input nodes. The bounds apply to works, a class of works passing causal trees and causal polytrees. The difficulty puting the bounds depends on the characteristics of the work. For directly works with binary goal nodes, tight bounds can puted in polynomial time. For other kinds of works, the derivation of tight bounds requires solving an integer program with a non-linear objective function, putationally intractable problem in the worst case. We provide a relaxation technique putes looser bounds in polynomial time for plex works. A brief description of an application of the probability bounds to the record linkage problem is provided. Index terms: works, Probability Bounds, Acquisition Cost, Sequential Decision Making 1. Introduction works are ing widely used in sequential decision making [Mookerjee and Mannino, 1997]. The objective in sequential decision problems is to maximize the expected payoff given beliefs about the state of nature and preferences about alternatives. The decision-maker can either make an immediate decision given current beliefs or make a costly observation to revise current beliefs. To reduce the cost of collecting inputs, the inference engine should detect when collecting additional inputs is not likely to change a decision. works are non-monotonic in that observing another input can increase or decrease the belief in a goal node. Thus it is difficult to detect when collecting more inputs can substantially change the belief in the goal. In this paper we study bounded, goal-directed queries that are a