A Tutorial On Theoretical Issues In Probabilistic Artificial Intelligence
Michael J. Kearns · 2005
In the last decade or so, many of the central problems of “classical” artificial intelligence — such as learning, planning and logical inference — have been reformulated in statistical or probabilistic frameworks. The benefits of this trend include the adoption of a common set of mathematical tools for the various AI subdisciplines, increased attention on algorithmic issues, and an emphasis on approximate methods for some notoriously hard exact AI problems. The trend also provides excellent opportunities for researchers from theoretical computer science to contribute to and influence AI. In this tutorial, I will survey these probabilistic frameworks and the basic computational problems posed in several well-developed areas of AI. I will describe some of the algorithms developed for these problems, overview what is formally known about them (and also what is suspected but not proven), and try to give a flavor of the mathematical techniques involved. The tutorial will be self-contained, designed to be accessible to anyone in the theory community, with an emphasis on the interesting open problems. Likely topics include: