1	Decisions Under Incomplete Representations & Reasoning Some Reflections Eric Horvitz Microsoft Research SADR Meeting on Decision Making in Complex Environments Cornell University April 5, 2003 horvitz@microsoft.com http://research.microsoft.com/~horvitz/
2	"Decision-theoretic systems in the real..." Decision-theoretic systems in the real world Decision support Autonomous decision making, embedded processes Some successes Decision making under bounded resources Inference and modeling Systems immersed in environments
3	Graphical Models and Decision Systems
4
5	Representing Problems of Action Influence diagrams (Howard & Matheson, 1975)
6	Representing Multiple Dimensions of Value
7	Beyond Single Shot Decisions
8	Partially Observable Markov Decision Process Representation
9	Real-World Applications
10	Scaling Up Bayesian Networks
11
12	Pulomonary/Sleep Apnea Integration with Physiological Monitoring
13	Fault Diagnosis and Troubleshooting
14
15	Great variation in execution time Very short and very long runs for different randomized runs on same instances Heavy-tailed distribution (Pareto)
16	Decisom Model for Dynamic Restart Policies To date: success with simple fixed policy: Restart search if run-time is greater than x Orders of magnitude speedup
17	Learning Bayesian Models + Decision-Theoretic Analysis Features Dynamic and static
18
19	Human-Computer Interaction
20	Monitoring Space Shuttle Telemetry
21
22	Inference about a User’s Time-Dependent Goals
23	Information Filtering & Alerting
24	Reasoning about Attention
25
26
27	Harnessing Multiple Classes of Evidence Speech recognizer confidence Correctness of natural language parse as evidence Visual analysis of pose
28	Intention, Attention, and Clarification Dialog
29
30
31	Assessing Preferences on Outcomes
32	Assessing Frustration with Number of Steps
33	But Still Cannot Solve Important Problems Intractability per problem size and structure Little experience with fielding autonomous, immersed decision making systems Poor understanding of subobtimality associated with incomplete models and inference
34	Hardness Inference is NP-Hard; approximation is NP-Hard Work on a tapestry of exact and approximate algorithms Exploit special structure, probe portions of model, restricted probabilistic relationships
35	A Tapestry of Approximation Algorithms
36	Reasoning Across Internal Medicine QMR-DT: Internal Medicine
37	"What do we do when..." What do we do when we cannot solve a decision problem completely? How do we trade computation time and value of computation? What is a complete problem? How do we reason about sensitivity of the MEU of action to refinement effort? Toward principles of decisions under bounded resources Simon: Inadequacy of MEU Good: Type II Rationality
38	Implementing Type II Rationality Under Limited Resources Need tractable meta-analysis of ideal nature and extent of reasoning Need characterizable approximation methods Need good understanding of cost of time, memory
39	"“Cost:”" “Cost:” “… … - C(t)” Influence of specific classes of cost on value of computation, comprehensive value of ultimate action Active inference about the structure of cost, expectation
40	Cost of Computational Resources Multiple cost contexts Urgency Deadline Urgent Deadline Uncertain Deadline Target
41	Time Criticality for Shuttle Propulsion
42	Inferring Costs of Delay
43	Context-Sensitive Costs
44	Characterizing the Value of Computation
45	Idealization..
46
47	Uncertain Quality, Cost, Resources
48	Models of Type II Rationality Example: Acute Respiratory Failure (ARF) vs. Respiratory Distress (RD)
49	Example: Acute Respiratory Failure (ARF) vs. Respiratory Distress (RD)
50	Bounding Conditioning Approximation: Acute Respiratory Failure vs. Respiratory Failure
51	Time-Critical Clinical Challenge
52	Time-Critical Clinical Challenge
53	A Dynamics of Belief and Action
54	A Dynamics of Belief and Action
55	A Dynamics of Belief and Action
56	A Dynamics of Belief and Action
57	A Dynamics of Belief and Action
58	"Understanding the influence of computational..." Understanding the influence of computational deliberation on expected value of ultimate action in world Analog to expected value of information Challenges: Tractable approximations
59
60	Expected Value of Computation (EVC) Computation procedure C Problem instance I Partial result p(I) Computation time r
61	EVC for Uncertain Inference
62	Deliberating About Computation versus Action
63
64	Reflective Decision-Theoretic Reasoning
65	"Reasoning about extent of EVC..." Reasoning about extent of EVC analysis Offline compilation, invoke multi-level real-time analyses? Overall: Ideal partition of resources to different phases of reasoning
66	Resource partition for phases of decision making
67	Understanding & Automated Modeling Processes Automated model construction Understand situation, deliberate like a decision analyst about distinctions and relationships Refinement of different dimensions of model
68	Methods for Constructing Models
69	Dynamic Construction of Pt-Specific Models
70	Dynamic Construction of Pt-Specific Models
71	Understanding Process of Model Construction Value of model refinement along different dimensions
72
73	"Conceptual refinement" Conceptual refinement
74	"Conceptual refinement" Conceptual refinement
75	"Conceptual refinement" Conceptual refinement
76	"Conceptual refinement" Conceptual refinement
77
78	Understanding Interactions Between Model Complexity and Inference Needs
79	Challenges Rational decision making under resource constraints—generalizations beyond special cases Harnessing EVI, EVR, EVC in parallel to guide decision making Autonomous decision systems immersed in an environment
80	Toward Bounded Optimality
81	Allocation of Resources to Streams of Decision Problems Over Time Environments typified by single challenges, bursts of challenges interspersed with idle time. Seek ideal approach to best leverage idle time. Applications to problem solving, communication under varying, limited resources
82	Stream of Problem Instances
83	Stream of Problem Instances
84	Stream of Problem Instances
85	Stream of Problem Instances
86	Personal Computing
87
88
89
90
91	Continual Computation How should time be spent? How should idle time be spent?
92
93
94	Expected Value of Precomputation Add consideration of uncertainty in future problem instances
95	EVP Flux of a Precomputation Strategy EVP Flux: Instantaneous rate at which EVP increases with precomputation
96
97
98
99
100	Trading Off Present for Future
101	Trading Off Present for Future
102	Trading Off Present for Future
103	Trading Off Present for Future
104	Trading Off Present for Future
105	Trading Off Present for Future
106	Trading Off Present for Future
107
108
109
110	Sequential Diagnostic Systems
111
112
113
114
115	Continual Computation for Prefetching Web Pages Utility models for partial documents Policies that maximize expected utility
116
117
118	"Modeling & inference under bounded..." Modeling & inference under bounded resources Characterizing incompleteness; understanding influence of model refinements, approximation on MEU of inferred A* Ideal allocation of resources to distinct dimensions of modeling refinement and reasoning, given cost of resources Embedded autonomous decision systems