A.M. TURING AWARD WINNERS BY...

United States – 2011

Short Annotated Bibliography

**Search and Heuristics**

- Pearl, J., “Asymptotic properties of minimax trees and game-searching procedures,”
*Artificial Intelligence*, 14, pp. 113–138, September 1980.*One of the first papers to establish “phase transition” properties for a combinatorial problem; introduced new mathematical techniques into the AI literature*. - Pearl, J., “Knowledge versus search: A quantitative analysis using A*,”
*Artificial Intelligence*, Vol. 20, pp. 1–13, 1983.*Proved the first results relating heuristic accuracy to search algorithm complexity.* - Pearl, J., “On the nature of pathology in game searching,”
*Artificial Intelligence*, Vol. 20, pp. 427–453, 1983.*Proved that, under the standard model of game trees, deeper search does not necessarily improve play; and showed that this paradox is resolved by correct probabilistic updating of beliefs.* - Karp, R. and J. Pearl, “Searching for an optimal path in a tree with random costs,"
*Artificial Intelligence*, Vol. 21, pp. 99–116, 1983.*Identified a phase transition property for a very simple path-finding problem, with significant complexity implications.* - Pearl, J., “On the discovery and generation of certain heuristics,”
*AI Magazine*, Winter/Spring, pp. 23–33, 1983.*The first paper on the systematic generation of admissible heuristics (lower bounds on optimal solution costs) by relaxing formally represented problem definitions; this idea led to dramatic advances in automated planning systems.* - Pearl, J.,
*Heuristics*:*Intelligent Search Strategies for Computer Problem Solving,*Addison-Wesley, 1984.*Synthesized essentially everything known up to that point about intelligent methods for search and game playing, much of it Pearl’s own work; also the first textbook to treat AI topics formally at a technically advanced level.* - Dechter, R. and J. Pearl, “Generalized best-first search strategies and the optimality of A*,”
*Journal of the Association for Computing Machinery*, Vol. 32, pp. 505–536, 1985. Available here.*Proved that A* is the most efficient member of a very broad class of problem-solving algorithms.*

**Bayesian Networks**

- Pearl, J., “Reverend Bayes on inference engines: A distributed hierarchical approach,”
*Proceedings, AAAI-82*, 1982.*The paper that began the probabilistic revolution in AI by showing how several desirable properties of reasoning systems can be obtained through sound probabilistic inference. It introduced tree-structured networks as concise representations of complex probability models, identified conditional independence relationships as the key organizing principle for uncertain knowledge, and described an efficient, distributed, exact inference algorithm.* - Kim, J. and J. Pearl, “A computational model for combined causal and diagnostic reasoning in inference systems,”
*Proceedings, IJCAI-83*, 1983.*Generalized the tree-structured network to allow for multiple parents, or causal influences, on any given variable.* - Pearl, J., “Learning hidden causes from empirical data,”
*Proceedings, IJCAI-85*, 1985.*Initiated the study of methods for learning the structure of probabilistic causal models.* - Pearl, J., “On the logic of probabilistic dependencies,”
*Proceedings, AAAI-86*, 1986.*One of several papers establishing the connection between graphical models and conditional independence relationships.* - Pearl, J., “Fusion, propagation and structuring in belief networks,”
*Artificial Intelligence*, Vol. 29, pp. 241–288, 1986.*The key technical paper on representation and exact inference in general Bayesian networks; by 1991 this had become the most cited paper in the history of the Artificial Intelligence journal.* - Pearl J. and A. Paz, “Graphoids: A graph-based logic for reasoning about relevance relations,” In B. du Boulay et al. (Eds.),
*Advances in Artificial Intelligence II*, North-Holland, 1987.*Establishes an axiomatic characterization of the properties that enable probabilities and other relational systems to be represented by graphs.* - Pearl, J., “Evidential reasoning using stochastic simulation of causal models,”
*Artificial Intelligence*, Vol. 32, pp. 245–258, 1987.*Derived a general approximation algorithm for Bayesian network inference using Markov chain Monte Carlo (MCMC); this was the first significant use of MCMC in mainstream AI.* - Pearl, J.,
*Probabilistic Reasoning in Intelligent Systems*, Morgan Kaufmann, 1988.*Explained the philosophical, cognitive, and technical basis for a probabilistic view of knowledge, reasoning, and decision making. One of the most cited works in the history of computer science, this book initiated the modern era in AI and converted many researchers who had previously worked in the logical and neural-network communities.*

**Causality**

- Pearl J. and T.S. Verma, “A theory of inferred causation,”
*Proceedings, KR-91*, 1991.*Introduces minimal-model semantics as a basis for causal discovery, and shows that causal directionality can be inferred from patterns of correlations without resorting to temporal information.* - Pearl, J., “Graphical models, causality, and intervention,”
*Statistical Science*, Vol. 8, pp. 266–269, 1993.*Introduces the back-door criterion for covariate selection, the first to guarantee bias-free estimation of causal effects.* - Pearl, J., “Causal diagrams for empirical research,”
*Biometrika*, Vol. 82, Num. 4, pp. 669–710, 1995.*Introduces the theory of causal diagrams and its associated do-calculus; the first (and still the only) mathematical method to enable a systematic removal of confounding bias in observations.* - Pearl, J., “The Art and Science of Cause and Effect,”
*UCLA Cognitive Systems Laboratory, Technical Report R-248*, 1996.*Transcript of lecture given Thursday, October 29, 1996, as part of the UCLA 81st Faculty Research Lecture Series. Used later as epilogue to the book Causality (2000). Provides a panoramic view of the historical development of causal thoughts from antiquity to modern days.* - Pearl, J.,
*Causality*:*Models, Reasoning, and Inference,*Cambridge University Press, 2000.*Building on theoretical results from 1987 to 2000, lays out a complete framework for causal discovery, interventional analysis and counterfactual reasoning, bringing mathematical rigor and conceptual clarity to an area previously considered off-limits for statistics. Winner of the 2001 Lakatos Prize for the most significant new work in the philosophy of science.* - Pearl, J., “The logic of counterfactuals in causal inference (Discussion of `Causal inference without counterfactuals' by A.P. Dawid),”
*Journal of American Statistical Association*, Vol. 95, pp. 428–435, 2000.*Demonstrates how counterfactual reasoning underlines scientific thought and argues against its exclusion from statistical analysis.* - Tian, J. and J. Pearl, “Probabilities of causation: Bounds and identification,”
*Annals of Mathematics and Artificial Intelligence*, Vol. 28, pp. 287–313, 2000.*Derives tight bounds on the probability that one observed event was the cause of another, in the legal sense of "but for," thus providing a principled way of substantiating guilt and innocence from data.* - Pearl, J., “Robustness of causal claims,”
*Proceedings, UAI-04*, 2004.*Offers a formal definition of robustness and develops a method for assessing the degree to which causal claims are robust to model misspecification.* - Pearl, J., “Direct and indirect effects,”
*Proceedings, UAI-01*, 2001.*Establishes the theoretical basis of modern mediation analysis. Derives the "Mediation Formula" and provides graphical conditions for the identification of direct and indirect effect.* - Tian, J. and J. Pearl, “A general identification condition for causal effects,”
*Proceedings, AAAI-02*, 2002.*Uses the do-calculus to derive a general graphical condition for identifying causal effects from a combination of data and assumptions.* - Halpern, J. and J. Pearl, “Causes and explanations: A structural-model approach—Parts I and II,”
*British Journal for the Philosophy of Science*, Vol. 56, pp. 843–887 and 889–911, 2005.*Establishes counterfactual conditions for one event to be perceived as the “actual cause” of another and for one event to provide an “explanation” of another.* - Pearl, J., “Causal inference in statistics: An overview,”
*Statistics Surveys*, Vol. 3, pp. 96–146, 2009.*Describes a unified methodology for causal inference based on a symbiosis between graphs and counterfactual logic.* - Pearl, J., “The algorithmization of counterfactuals,”
*Annals of Mathematics and Artificial Intelligence*, Vol. 61, pp. 29–39, 2011.*Describes a computational model that explains how humans generate, evaluate and distinguish counterfactual statements so swiftly and consistently.* - Pearl J. and E. Bareinboim, “Transportability of causal and statistical relations: A formal approach,”
*Proceedings, AAAI-11*, 2011.*Reduces the classical problem of external validity to mathematical transformations in the do-calculus, and establishes conditions under which experimental results can be generalized to new environments in which only passive observation can be conducted.*