Click here to access pdf file (319 pages).
Click here to access Postscript file (319 pages).
Also listed as Technical Report KSL-90-76, Computer Science Department, Stanford University, December 1990.
Keywords: Bounded optimality, principles of bounded optimal systems, action under scarce resources, rationality, decision-theoretic reasoning, Bayesian networks, probabilistic inference, bounded rationality.
In the dissertation work, I explored foundations of flexibility of computation, probing the multiattribute utility of partial results and the trajectories through a multiattribute space that algorithms generate in return for resources.
I examined a variety of algorithms from the perspective of maximizing the expected utility of computation under resource constraints. Here is a figure displaying data generated by Protos/Algo as it probed the value of partial results generated by alternative sorting algorithms. A partial sort is depicted by a set of points in a two dimensional represenation where one axis is the key of records and the other are the locations of the records. A diagonal line represents a completely sorted file.
Here is another depiction of the value of partial results with flexible computation, now exploring the traveling salesperson problem (TSP), an NP-Hard task. We show the performance over time of a two-opt approximation. In the context of a loss function, representing the cost of waiting for an increasingly better tour, we compute a net value, the curve appearing in the middle of the graph. This work was done with Adrian Klein.
The primary focus of the dissertation is the exploration of rationality under resource constraints. The Protos system was built to explore the control of decision-theoretic inference in time-critical contexts. The system continues to compute an approximation for the expected value of computation (EVC) and decides whether to continue to compute or to act in the world. Here is some output from Protos after the system tackled a time-pressured medical decision. The upper left-hand corner displays the tightening of bounds over a probability needed to solve a decision problem. The larger graph displays several pieces of information about the state of the problem when the system decided to act in the world rather than continue to refine its result.
Click here for additional background.