Massachusetts Institute of Technology

Department of Electrical Engineering and Computer Science

Proposal for Thesis Research in Partial Fulfillment of the Requirements for the Degree of Master of Science

Michael P. Frank ^{∗} Laboratory for Computer Science Massachusetts Institute of Technology mpf@medg.lcs.mit.edu February 11, 1993

\underline{Title:} Rational Partial Evaluation of Decision Trees Submitted by: Michael P. Frank

305 Memorial Drive Cambridge, MA 02139

(Signature of Author)

\underline{Date of Submission:} February 11, 1993 \underline{Expected Data of Completion:} December, 1993 \underline{Laboratory where thesis will be done:} MIT Laboratory for Computer Science Supervision Agreement:

The program outlined in this proposal is adequate for a Master’s thesis. The supplies and facilities required are available, and I am willing to supervise the research and evaluate the thesis report.

Jon Doyle, Principal Research Scientist

MIT Laboratory for Computer Science

∗This material is based upon work supported under a National Science Foundation Graduate Fellowship. Any opinions, findings, conclusions or recommendations expressed in this publication are those of the author and do not necessarily reflect the views of the National Science Foundation. The work herein is also supported in part by the USAF Rome Laboratory and DARPA under contract F30602-91-C-0018.

Contents

1 Introduction 2

2 Relation to Existing Work 2

3 Research Plan 3 3.1 January to March . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3.2 April to August . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3.3 September to December . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

4 Future Work 4

1 Introduction

Expert decision-making systems often evaluate decision trees to determine what action has the best expected utility. But sometimes the decision tree implied by the system’s model of the domain is intractably large; not only too large to store explicitly, but also too large to evaluate in a reasonable time. System designers typically avoid such difficulties by simplifying the model of the domain so that it will not produce large decision trees, or by abandoning decision trees when they are too large and using some other method to come to a decision.

An alternative, explored in this research, is to partially evaluate the decision tree, using estimates for the utilities of non-leaf nodes. This is analogous to the standard computer game-playing (CGP) technique of partially evaluating the typical intractably-large game trees.

The problem now (as in game tree search) becomes two: estimating utilities of non-leaf nodes, and exploring those parts of the tree that are expected to contribute the most to the quality of the overall decision.

In CGP, the problem of tree-search can be partially handled using cheap and provably-correct algorithms such as Alpha-Beta and Scout. Recently, researchers have gone further with methods that use information about the degree of uncertainty of utility estimates to select those search actions that will most improve the quality of the overall decision. These methods have met with some success. Especially appropriate are the decision-theoretic metareasoning techniques of Russell and Wefald, which search those parts of the tree expected to contribute the most to the utility of the final decision.

Can this sort of decision-theoretic metareasoning be profitably used to control the partial evaluation of large decision trees? That is the primary question that this research will explore.

2 Relation to Existing Work

Although this research will be based in part on Russell and Wefald’s metareasoning techniques, it will go beyond that work in several ways.

• This work will focus on decision trees rather than game trees, leading to somewhat different details for the propagation of utilities.

• I intend to reevaluate some of the simplifying assumptions Russell and Wefald make, and make different and hopefully more general assumptions of my own.

• I plan to generalize their representations of probability distributions over future utilities.

• I plan to make an abstract characterization of the metareasoning problem, with a clear interface between the metareasoning strategy and the non-metareasoning parts of the algorithm, so that different metareasoning strategies can be plugged in and their effectiveness compared. I will investigate several alternative metareasoning strategies and compare them.

• I will focus on demonstrating that metareasoning is actually helpful. In particular, if the metareasoning overhead causes the system to perform poorly in comparison with a nonmetareasoning evaluation strategy, that will be considered unacceptable. I hope to make a metareasoning module that can adjust the amount of time spent in metareasoning so as not to decrease overall performance.

• I hope to make a clean, elegant implementation of the system that will be useful for pedantic purposes.

• I hope to apply these techniques in a large, real-world domain such as medical decision-making as well as in a small, well-defined domain such as game-playing.

I hope to also make use of decision-theoretic control techniques developed by other researchers such as Pearl, Horvitz, Heckerman, Hansson and Mayer, and others. From preliminary investigations, much of that work seems very relevant.

3 Research Plan

My research on this topic, which has already started, will continue throughout this year and should be completed in December. I have divided this year into three periods during which I will focus on different phases of the work. Work I have planned to do during these periods is summarized below.

3.1 January to March

In this period I will research existing work on techniques for evaluation of problems involving large decision trees. In addition, I will study and become acquainted with the existing research on the application of decision-theoretic control techniques to large search and game-playing problems.

This work will involve talking to experts in application of AI to real-world decision-making problems, such as Steve Pauker at NEMC. In these discussions I hope to learn more about the nature of the large decision problems encountered, to learn about the problems with the use of existing techniques, and to determine to what degree my own approach would be appropriate for various kinds of real-world decision problems.

I also plan to look into the computer-game playing research relevant to one-player games with chance, to determine whether partial evaluation of decision trees would be a profitable approach in that domain as well, and if so, to study other techniques against which to make objective comparisons of performance. Also, there is the possibility that I may find some techniques in the solitaire-playing literature that could be applied to some real-world decision problems.

Also, I will study in detail the metareasoning work of Russell & Wefald, Horvitz, Hansson & Mayer, and others, to thoroughly learn how to correctly apply decision theory to the selection and control of computational actions when searching for approximate solutions to hard problems.

3.2 April to August

During this period I will focus on the detailed development of my techniques for partial evaluation of decision trees, incorporating what I will have learned about the nature of the decision problems that I think my techniques will be best suited to address, and incorporating what I will have learned about rational control of computation.

I will also design and implement a program for testing these ideas on example problems in various domains. I hope to be able to compare the performance of my system with that of existing approaches.

3.3 September to December

In this final period I will write the thesis. It will describe in detail the motivation for the work, the mathematical basis for the metareasoning techniques, the design and implementation of the system for solving large decision problems, and the results of experiments involving the system. It will also point towards possible directions for related research.

4 Future Work

I plan to continue and generalize this work, or something closely related, for my Ph.D. work. For example, I would like to explore the design of reflective systems that can reason effectively about their own past and future computational behavior, including their reflective behavior, and act rationally to change what their future behavior will be. The ultimate goal would be a system that knew enough about itself, and about programming, that it could adaptively refine or restructure parts of itself, with the aim of improving its own performance. Such a system would greatly facilitate further development of complex AI programs.

References

[1] Eric B. Baum and Warren D. Smith. Best play for imperfect players and game tree search. Draft report, NEC Research Institute, 4 Independence Way, Princeton, NJ 08540, March 1993.

[2] Ronald J. Bodkin. Extending computational game theory: Simultaneity, multiple agents, chance and metareasoning. Master’s thesis, Massachusetts Institute of Technology, September 1992.

[3] John S. Breese and Eric J. Horvitz. Reformulating and solving belief networks under bounded resources. Technical Report KSL-90-28, Knowledge Systems Laboratory, Stanford University, March 1990.

[4] Hollis J. Call and William A. Miller. A comparison of approaches and implementations for automating decision analysis. Reliability Engineering and System Safety, 30:115–162, 1990.

[5] Jim des Rivieres and Brian Cantwell Smith. The implementation of procedurally reflective languages. Technical Report CSLI-84-9, Center for the Study of Language and Information, Ventura Hall, Stanford University, Stanford, CA 94305, November 1984.

[6] Michael Frank. The limits of bayesianism. Draft report, Laboratory for Computer Science, MIT, May 1992.

[7] Bjorn Gamback, Manny Rayner, and Barney Pell. An architecture for a sophisticated mechanical bridge player. Draft report, Knowledge Based Systems Laboratory, Swedish Institute of Computer Science.

[8] Matthew L. Ginsberg and Donald F. Geddis. Is there any need for domain-dependent control information? In Proceedings Ninth National Conference on Artificial Intelligence, 1991.

[9] G. Anthony Gorry. Computer-assisted clinical decision making. Methods of Information in Medicine, 12:45–51, 1973.

[10] G. Anthony Gorry, Jerome P. Kassirer, Alvin Essig, and William B. Schwartz. Decision analysis as the basis for computer-aided management of acute renal failure. The American Journal of Medicine, 55:473–484, October 1973.

[11] Othar Hansson, Gerhard Holt, and Andrew Mayer. Experiments with a decision-theoretic scheduler. In Proceedings of the AAAI Spring Symposium on Practical Approaches to Planning, Scheduling and Control, Stanford, California, March 1992.

[12] Othar Hansson and Andrew Mayer. The optimality of satisficing solutions. In Proceedings of the Fourth Workshop on Uncertainty in Artificial Intelligence, August 1988.

[13] Othar Hansson and Andrew Mayer. Heuristic search as evidential reasoning. In Proceedings of the Fifth Workshop on Uncertainty in Artificial Intelligence, Windsor, Ontario, August 1989.

[14] Othar Hansson and Andrew Mayer. Probabilistic heuristic estimates. Annals of Mathematics and Artificial Intelligence, 2:209–220, 1990.

[15] Othar Hansson, Andrew Mayer, and Stuart Russell. Decision-theoretic planning in bps. In Proceedings of the AAAI Spring Symposium on Planning in Uncertain, Unpredictable, or Changing Environments, Stanford, California, March 1990.

[16] David Heckerman and Holly Jimison. A perspective on confidence and its use in focusing attention during knowledge acquisition. In Proceedings of the Third Workshop on Uncertainty in Artificial Intelligence, pages 123–131, Seattle, WA, 1987.

[17] David E. Heckerman, Eric J. Horvitz, and Bharat N. Nathwani. Toward effective normative decision systems: Update on the pathfinder project. Technical Report KSL-89-25, Knowledge Systems Laboratory, Stanford University, March 1989.

[18] Eric J. Horvitz. Reasoning under varying and uncertain resource constraints. Technical Report KSL-88-35, Knowledge Systems Laboratory, Stanford University, April 1988.

[19] Eric J. Horvitz. Rational metareasoning and compilation for optimizing decisions under bounded resources. Technical Report KSL-89-81, Knowledge Systems Laboratory, Stanford University, August 1990.

[20] Eric J. Horvitz and John S. Breese. Ideal partition of resources for metareasoning. Technical Report KSL-90-26, Knowledge Systems Laboratory, Stanford University, March 1990.

[21] Eric J. Horvitz, John S. Breese, and Max Henrion. Decision theory in expert systems and artificial intelligence. Technical Report KSL-88-13, Knowledge Systems Laboratory, Stanford University, February 1988.

[22] Eric J. Horvitz, Gregory F. Cooper, and David E. Heckerman. Reflection and action under scarce resources: Theoretical principles and empirical study. Technical Report KSL-89-01, Knowledge Systems Laboratory, Stanford University, May 1989.

[23] Eric J. Horvitz, H. Jacques Suermondt, and Gregory F. Cooper. Bounded conditioning: Flexible inference for decisions under scarce resources. Technical Report KSL-89-42, Knowledge Systems Laboratory, Stanford University, September 1990.

[24] Donald E. Knuth and Ronald W. Moore. An analysis of alpha-beta pruning. Artificial Intelligence, 6:293–326, 1975.

[25] Nicholas Kushmerick, Steve Hanks, and Daniel Weld. An algorithm for probabilistic planning. Draft Report, Department of Computer Science and Engineering, University of Washington, January 1993.

[26] Tze-Yun Leong. Toward a general framework for automated dynamic decision making. Ph.D. thesis proposal, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, February 1993.

[27] Monroe Newborn. Computer chess: Ten years of significant progress. Advances in Computers, 29:197–248, 1989.

[28] Judea Pearl. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley series in Artificial Intelligence. Addison-Wesley, 1984.

[29] Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Mateo, CA, 1988.

[30] Barney Pell. Metagame: A New Methodology for Games and Learning. PhD thesis, Trinity College, University of Cambridge, August 1992. Unpublished draft.

[31] Barney Pell. Metagame in symmetric chess-like games. In H. J. van den Herik and L. V. Allis, editors, Heuristic Programming in Artificial Intelligence 3—The Third Computer Olympiad. Ellis Horwood, 1992.

[32] Start Russell and Eric Wefald. Decision-theoretic control of reasoning: General theory and an application to game-playing. Draft report, Computer Science Division, University of California, Berkeley, CA 94270, October 1988.

[33] Stuart Russell. Fine-grained decision-theoretic search control. In Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence, 1990.

[34] Stuart Russell and Eric Wefald. A meta-greedy game-playing algorithm. Draft report, Computer Science Division, University of California, Berkeley, CA 94720, March 1988.

[35] Stuart Russell and Eric Wefald. On optimal game-tree search using rational meta-reasoning. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, pages 334–340, 1989.

[36] Stuart Russell and Eric Wefald. Principles of metareasoning. Artificial Intelligence, 49:361–395, 1991.

[37] William B. Schwartz, G. Anthony Gorry, Jerome P. Kassirer, and Alvin Essig. Decision analysis and clinical judgement. The American Journal of Medicine, 55:459–472, October 1973.

[38] David E. Smith. A decision-theoretic approach to the control of planning search. Technical Report LOGIC-87-11, Stanford Logic Group, Department of Computer Science, Stanford University, January 1988.

[39] Michael P. Wellman. Formulation of tradeoffs in planning under uncertainty. Ph.D. Thesis MIT/LCS/TR-427, Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, Massachusetts 02139, August 1988.

[40] Michael P. Wellman and Jon Doyle. Modular utility representation for decision-theoretic planning. In James Hendler, editor, Artificial Intelligence Planning Systems: Proceedings of the First International Conference, pages 236–242, June 1992.

[41] Michael P. Wellman, Mark H. Eckman, Craig Fleming, Sharon L. Marchall, Frank A. Sonnenberg, and Stephen G. Pauker. Automated critiquing of medical decision trees. Medical Decision Making, 9:272–284, 1989.

[42] John B. Wong, Frank A. Sonnenberg, Deeb N. Salem, and Stephen G. Pauker. Myocardial revascularization for chronic stable angina: Analysis of the role of percutaneous transluminal coronary angioplasty based on data available in 1989. Annals of Internal Medicine, 113(11):852– 871, December 1990.