Uncertainty / Probability

(a subtopic of Reasoning)

18th-century theory is new force in computing. By Michael Kanellos. CNET News.com (February 18, 2003). "Thomas Bayes, one of the leading mathematical lights in computing today, differs from most of his colleagues: He has argued that the existence of God can be derived from equations. His most important paper was published by someone else. And he's been dead for 241 years. Yet the 18th-century clergyman's theories on probability have become a major part of the mathematical foundations of application development. Search giant Google and Autonomy , a company that sells information retrieval tools, both employ Bayesian principles to provide likely (but technically never exact) results to data searches. ... 'Bayesian research is used to make the best gambles on where I should flow with computation and bandwidth,' said Eric Horvitz, senior researcher and group manager of the Adaptive Systems & Interaction Group at Microsoft Research. 'I personally believe that probability is at the foundation of any intelligence in an uncertain world where you can't know everything.' ... Bayesian theory can roughly be boiled down to one principle: To see the future, one must look at the past. Bayes theorized that the probability of future events could be calculated by determining their earlier frequency. ... A related technique, called Hidden Markov models, allows probability to anticipate sequences. A speech recognition application, for example, knows that the sound most likely to follow 'q' is 'u.'"

• Also see: Improving the search for intelligence. By Paul Marks. New Scientist (February 12, 2007 | Issue 2590: pages 22 - 23; subscription req'd). "Detective Gary Williams was investigating a rape last year when his leads dried up. From the victim's statement, he knew there had been a witness to the crime, he even knew his name, but the person had not come forward and could not be found at their registered address. So Williams, of South Yorkshire Police in the UK, turned to a smart search engine the force had begun trialling only 2 hours earlier. With just the name of the witness, the Intelligent Data Operating Layer (IDOL) [developed by Autonomy of Cambridge, UK,] trawled the force's database. ... IDOL uses statistical techniques to return information and phrases related to, but not necessarily including, the search terms entered. ... The system harnesses a probability theory developed by Thomas Bayes, an English cleric and mathematician, in the 18th century. ... Autonomy is now extending the system to telephone calls. It has combined IDOL with speech-recognition software to create a voice-to-text system that translates calls made to the police into searchable statements."
• Visit Autonomy and check out their Technology Overview.

Reasoning Under Uncertainty. From Artificial Intelligence, by David B. Leake, Indiana University [to appear, Van Nostrand Scientific Encyclopedia, Ninth Edition, Wiley, New York, 2002]. "[I]n order to draw useful conclusions, AI systems must be able to reason about the probability of events, given their current knowledge.... Research on Bayesian reasoning provides methods for calculating these probabilities. Bayesian networks, graphical models of the relationships between variables of interest, have been applied to a wide range of tasks, including natural language understanding, user modeling, and medical diagnosis."

Association for Uncertainty in Artificial Intelligence (AUAI) homepage. Click on "Resources" and check out their collection of tutorials and surveys. "Tutorials are nominated by present and former members of the UAI program committee."

AI on the Web: Reasoning with Uncertainty. A resource companion to Stuart Russell and Peter Norvig's "Artificial Intelligence: A Modern Approach" with links to reference material, people, research groups, books, companies and much more.

A Brief Introduction to Graphical Models and Bayesian Networks. By Kevin Murphy, a postdoc at the MIT AI lab. A great place to start regardless of your level of familiarity!

Whatever happened to machines that think? By Justin Mullins. New Scientist (April 23, 2005; Issue 2496: pages 32 - 37). "The renewed confidence stems from a new breed of systems that can deal with uncertainty - something humans have little trouble with, but which has till now brought computer programs grinding to a halt.... Systems using the mathematical technique known as Bayesian inference have improved the performance of many AI programs to the point where they can be used in the real world."

Stuart Russell on the Future of Artificial Intelligence. Ubiquity; Volume 4, Issue 43 (December 24 - January 6, 2004). "UBIQUITY: Will they be based on a probability theory? RUSSELL: Yes. Speech has already gone this route. Speech recognition is a giant calculation of posterior probabilities from evidence. ... At the same time, logical AI tradition has broadened to include probability theory. A lot of high-level representation, reasoning and planning can go on in a probabilistic formalism."

Bayes Offers a 'New' Way to Make Sense of Numbers. A 236-year-old approach to statistics is making a comeback, as its ability to factor in hunches as well as hard data finds applications from pharmaceuticals to fisheries. By David Malakoff. (1999). Science Magazine, Volume 286, Number 5444; 1460-1464. "Advances in computers and the limitations of traditional statistical methods are part of the reason for the new popularity of this old approach. But researchers say the Bayesian approach is also appealing because it allows them to factor expertise and prior knowledge into their computations--something that traditional methods frown upon."

MIT Computational Cognitive Science Group: "We study the computational basis of human learning and inference. ... We approach these topics with a range of empirical methods -- primarily, behavioral testing of adults, children, and machines -- and formal tools -- drawn chiefly from Bayesian statistics and probability theory...."

• Several papers can be accessed online from the home page of Josh Tenenbaum, Group Leader.

Who was Thomas Bayes?                Who was Andrei Andreyevich Markov?

See our Namesakes page!

Causality: Models, Reasoning, and Inference. By Judea Pearl (Cambridge University Press, March 2000). "The two fundamental questions of causality are: (1) What empirical evidence is required for legitimate inference of cause-effect relationships? (2) Given that we are willing to accept causal information about a phenomenon, what inferences can we draw from such information, and how? ... This book provides a systematic account of this causal transformation, addressed primarily to readers in the fields of statistics, artificial intelligence, philosophy, cognitive science, and the health and social sciences." - from the Preface. "Links are provided to intoductory sections of all chapters and to selected sections of general interest.

Probabilistic Research. Professor David Poole, Department of Computer Science, University of British Columbia. "This file contains some information on research by David Poole, and students on probabilistic reasoning and decision making. It is not intended to be an introduction to the vast literature on these topics, but only the incremental work done by me."

Learning, Logic, and Probability: a video of Pedro Domingos' talk at CSE Colloquia - 2005, The University of Washington Computer Science & Engineering Colloquium Series, available from the ResearchChannel ("a non-profit organization founded in 1996 by a consortium of leading research universities, institutions and corporate research centers dedicated to creating a widely accessible voice for research through video and Internet channels").

Planning Under Uncertainty. Professor Thomas Dean, Department of Computer Science, Brown University. "The focus of this research project is on planning under uncertainty using Markov decision processes. The main application areas is the design of automated planning and control systems for stochastic domains including mobile robotics. The theoretical emphasis is on algorithms for solving Markov decision processes with very large state and action spaces."

Building thinking robotics for the real world. IST Results (December 15, 2004). "Researchers at the Bayesian Inspired Brain and Artefacts (BIBA) project are using a novel application of Bayesian reasoning to design artefacts (objects produced or shaped by human craft) that can learn to act rationally with incomplete information. ... BIBA project researchers use Bayesian reasoning to understand the behaviour of animals and then apply this same logic to create artefacts for the 'real world'. Pierre Bessière, Scientific Manager of the IST programme-funded BIBA project at INRIA’s GRAVIR laboratory in France explains: 'Both living organisms and robotic systems face the difficulty of how to use an incomplete model of their environment to perceive, infer, decide and act efficiently.' ... BIBA researchers developed probabilistic programming methods for the Cycab that use biologically plausible techniques to define the obstacle avoidance system as a survival instinct. The goal is to create a completely automatic car that doesn’t need a human driver and can safely navigate streets that are beset with unpredictable occurrences."

Hidden Markov Models Tutorial from the School of Computing, University of Leeds. "Often we are interested in finding patterns which appear over a space of time. These patterns occur in many areas; the pattern of commands someone uses in instructing a computer, sequences of words in sentences, the sequence of phonemes in spoken words - any area where a sequence of events occurs could produce useful patterns. ... This is typical of the type of system we will consider in this tutorial. * First we will introduce systems which generate probabalistic patterns in time, such as the weather fluctuating between sunny and rainy. * We then look at systems where what we wish to predict is not what we observe - the underlying system is hidden. In the above example, the observed sequence would be the seaweed and the hidden system would be the actual weather. * We then look at some problems that can be solved once the system has been modeled."

Bayesian Networks without Tears. Eugene Charniak (1991). AI Magazine 12(4):50-63. "I give an introduction to Bayesian networks for AI researchers with a limited grounding in probability theory. Over the last few years, this method of reasoning using probabilities has become popular within the AI probability and uncertainty community. ... The best way to understand Bayesian networks is to imagine trying to model a situation in which causality plays a role but where our understanding of what is actually going on is incomplete, so we need to describe things probabilistically."

MS Office Helper Not Dead Yet. By Leander Kahney. Wired News (April 19, 2001). "Clippy, the Microsoft Office character that pops up to assist users -- often at the least-helpful times -- won't automatically show up in Office XP. But a Microsoft researcher working on the logic behind Clippy said that, although the implementation may be off, the technology it is based on is one the company's cornerstones for future products.Academics agree that Bayesian logic is about to become one of the most pervasive techniques used in computing.Bayesian logic is a set of mathematical principles outlined by an obscure but brilliant Presbyterian minister and amateur mathematician, Thomas Bayes, who lived in 18th century England.... In the last five years, Bayesian logic has breathed new life into artificial intelligence, shaken up mathematics and revolutionized drug research. It is also used in systems to pilot space shuttles and to spot credit card fraud. And that's only scratching the surface. ... In computer science, Bayesian techniques are used to build complex 'belief' networks that represent problems or situations as associations of inter-linked causes and effects. Belief networks allow machines to represent complex problems and make decisions based on conditions that aren't always clear-cut. Bayesian logic is being applied to AI, which has been hampered by programs that are inflexible and intolerant of ambiguity. ... [Eric] Horvitz said this next generation of Microsoft software includes an information manager that uses Bayesian logic to filter e-mail, voice messages, pages and other information for mobile users."

• Also see: Formula for 'Clippy' originated centuries ago. Reuters. Available from CNN.com. (April 12, 2001) "Roughly speaking, Bayes' theorem adds common sense to the maths used to work out how likely something is. It introduces yes-no computers to grey areas, doubt and best guesses."

"B-Course is a web-based interactive tutorial on Bayesian modeling, in particular dependence modeling. However, it is more than just a tutorial. It is also a free data analysis tool that makes it possible for you to use your own data as example data for the tutorial." Available from The Complex Systems Computation Group(CoSCo), Department of Computer Science, University of Helsinki.

Bayesian Belief Nets. A collection of resources from Russell Greiner that includes articles from the popular press, tutorials, applications, research groups and much more.

Probabilistic Thinking. By Professor Richard Jeffrey, Professor Emeritus, Princeton; Visiting Distinguished Professor of Social Science, UCI. "Probabilistic thinking was a mid-17th century artifact originating in a famous correspondence between Fermat and Pascal -- a correspondence on which Huygens based a widely read textbook: On Calculating in Games of Luck (1657). The probabilistic framework didn't exist until those people cobbled it together. It remains in use today, much as in Huygens's book. " -from the Preface

Reasoning under Uncertainty in Medical Decision-Support Systems. From the Center for Advanced Medical Informatics at Stanford (CAMIS). "Medicine is replete with uncertainty. In particular, there is uncertainty due to incomplete and inexact scientific models of human health and disease, and there is uncertainty secondary to incomplete and erroneous data about individual patients. We are exploring the use of probability theory as a representation of uncertainty in medical diagnostic systems."

Comparison of rule-based and Bayesian network approaches in medical diagnostic systems. By Agnieszka Onisko, Peter Lucas,and Marek J. Druzdzel. In Artificial Intelligence in Medicine (AIME2001), S. Quaglini, P. Barahona, S. Andreassen, editors. 2001. Springer-Verlag Heidelberg. Available in several formats from CiteSeer.IST. Abstract: " Almost two decades after the introduction of probabilistic expert systems, their theoretical status, practical use, and experiences are matching those of rule-based expert systems. Since both types of systems are in wide use, it is more than ever important to understand their advantages and drawbacks. We describe a study in which we compare rule-based systems to systems based on Bayesian networks. We present two expert systems for diagnosis of liver disorders that served as the inspiration and vehicle of our study and discuss problems related to knowledge engineering using the two approaches. We finally present the results of a simple experiment comparing the diagnostic performance of each of the systems on a subset of their domain."

Gister-CL: An Evidential Reasoning System. "SRI's work in automated uncertain reasoning emphasizes the practical application of theoretically sound techniques for reasoning from evidence-that is, information that is potentially incomplete, inexact, inaccurate, and from diverse sources. SRI pioneered evidential reasoning for drawing conclusions from multiple sources of evidential information about dynamic real-world situations." In addition to an overview, you'll find lots of links to the technologies involved and the related applications.

• Be sure to see possibilistic reasoning: "Possibilistic methods exploit the relations of similarity and of relative preference between alternate explanations of the evidence."

"The Society for Artificial Intelligence and Statistics is a nonprofit organization, incorporated in New Jersey (USA), dedicated to facilitating interactions between researchers in AI and Statistics."

More Readings

Probabilistic Algorithms in Robotics. By Sebastian Thrun. AI Magazine 21(4): Winter, 2000, 93-109. "This article describes a methodology for programming robots known as probabilistic robotics. The probabilistic paradigm pays tribute to the inherent uncertainty in robot perception, relying on explicit representations of uncertainty when determining what to do. This article surveys some of the progress in the field, using in-depth examples to illustrate some of the nuts and bolts of the basic approach. My central conjecture is that the probabilistic approach to robotics scales better to complex real-world applications than approaches that ignore a robot’s uncertainty."

Resolution of Uncertainty in Prefrontal Cortex. By Wako Yoshida and Shin Ishii. Neuron 50: 781-789, June 2006. "Making optimal decisions in the face of uncertain or incomplete information arises as a common problem in everyday behavior, but the neural processes underlying this ability remain poorly understood. ... Here, we use functional magnetic resonance imaging during a maze navigation task to study neural activity relating to the resolution of uncertainty as subjects make sequential decisions to reach a goal. We show that distinct regions of prefrontal cortex are engaged in specific computational functions that are well described by a Bayesian model of decision making. This permits efficient goal-oriented navigation and provides new insights into decision making by humans."