Theoretical Issues in Probabilistic Artificial Intelligence
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 frameworks with statistical
or probabilistic underpinnings. The benefits of this trend include
the adoption of a common set of mathematical tools for the various
AI subdisciplines, increased attention on central algorithmic issues,
an emphasis on approximation algorithms for some notoriously hard
AI problems... and excellent opportunities for researchers from the
theoretical computer science community to contribute to and influence AI.
In this tutorial, I will survey the probabilistic frameworks and the
central computational problems posed in several well-developed areas
of AI. I will describe some of the algorithms proposed 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 STOC/FOCS community, with an emphasis
on the interesting open problems. Likely topics include:
Graphical Models and Probabilistic Inference: graph-theoretic
representations of distributions; the junction tree algorithm for
exact inference in sparse networks; variational methods from
statistical physics for approximate inference in dense networks.
Markov Decision Processes for Planning and Reinforcement Learning:
planning in MDP's via value iteration, linear programming, and sparse
sampling; the Q-learning algorithm; the exploration-exploitation
trade-off and mixing times.
Supervised Learning: basics and recent advances in boosting; maximum
margin analyses of generalization error.