Natively probabilistic computation

摘要: I introduce a new set of natively probabilistic computing abstractions, including generalizations Boolean circuits, backtracking search and pure Lisp. show how these tools let one compactly specify generative models, generalize parallelize widely used sampling algorithms like rejection Markov chain Monte Carlo, solve difficult Bayesian inference problems. I first Church, programming language for describing processes that induce distributions, which generalizes Lisp, deterministic procedures functions. highlight the ways randomness meshes with reflectiveness Lisp to support representation structured, uncertain knowledge, nonparametric models from current literature, programs decision making under uncertainty, learn very simple data. then systematic stochastic search, recursive algorithm exact approximate popular form broader setting simulation recovers particle filters as special case. use it reasoning problems statistical physics, causal stereo vision. Finally, digital circuits model probability algebra just traditional algebra. can be build massively parallel, fault-tolerant machines allow efficiently run Carlo methods on hundreds thousands variables in real time. emphasize ideas fit together into coherent software hardware stack computing, organized around distributions samplers rather than argue by building uncertainty foundations our languages machines, we may arrive at ones are more powerful, flexible efficient designs, better alignment needs computational science, statistics artificial intelligence. (Copies available exclusively MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)