An Overview of Some Recent Developments in Bayesian Problem-Solving Techniques

Article excerpt

The past five years or so have seen increased interest and tremendous progress in the development of Bayesian techniques for building problem-solving systems. We have come a long way since the Uncertainty in AI Workshop was founded in 1985, an event precipitated in large part by the fact that the mainstream AI community at that time considered probabilistic approaches impractical for building intelligent systems. Since then, the workshop has become the Conference on Uncertainty in AI, attracting highquality contributions from researchers in a broad array of disciplines, including AI, statistics, operations research, and decision science. In the last several years, concepts from Bayesian decision theory, along with representational and computational techniques developed within the uncertainty in AI community, have found their way into mainstream AI and are appearing more and more routinely in papers not focused primarily on uncertainty. Areas include vision, natural language processing, robot navigation, planning, and machine learning. One sign of the importance now regarded Bayesian techniques in building and analyzing software systems is the fact that the Journal of the ACM recently introduced a track on decisions, uncertainty, and computation.

Bayesian decision theory, like much of AI, is concerned with the characterization of rational behavior. According to Bayesian decision theory (Savage 1954), a choice situation is characterized by a set of possible acts A, a probability distribution P over the set of possible states of the world S, the outcome of each act in each possible state a(s), and a utility function u over the outcome space. The optimal act is the one that maximizes expected utility:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Acts here can be physical actions, speech acts, deliberative acts, or complex plans composed of various kinds of action. Decision theory is interesting for AI because it provides a normative theory for designing agents capable of reasoning and acting under conditions of uncertainty. This normativity is expressed in the form of a representation theorem stating that if an agent's preferences obey a set of intuitively appealing constraints, then there exists a probability function P and a utility function U, such that the most preferred action is the one that maximizes expected utility. However, what decision theory does not provide are the computational mechanisms for building rational agents and the representations suited to engineering their knowledge bases. These issues have been the primary focus and contribution of the work conducted by uncertainty researchers in AI. In this introduction, I discuss issues in the elicitation, representation, and manipulation of probability models. I provide a brief discussion of Bayesian networks and then cover applications of Bayesian techniques, knowledge-based-model construction and structured representations, and learning of graphic probability models. More recently, researchers have begun to explore these same issues with regard to utility models. The article by Jon Doyle and Richmond Thomason and the one by Jim Blythe provide some discussion of this work. In the interests of brevity, in this introduction I omitted discussion of exciting and valuable research contributions in many other subareas. I point the interested reader to the proceedings of the Conference on Uncertainty in AI (Cooper and Moral 1998), the Workshop on AI and Statistics (Heckerman and Whittaker 1999), and the web page of the Association for Uncertainty in AI (www.auai.org) for further reading.

Bayesian Networks

The Bayesian network formalism is the single development most responsible for progress in building practical systems capable of handling uncertain information. The first book on Bayesian networks (Pearl 1988) was published just over 10 years ago, and since then, several other textbooks have appeared (Castillo, Gutierrez, and Hadi 1997; Jensen 1996; Neapolitan 1990). …