AAAI 2013 Tutorial: Symbolic Methods for Probabilistic Inference, Optimization, and Decision-making
Speaker:
Abstract:
This tutorial explores recent advances in symbolic data structures for exact probabilistic inference and decision-making in
mixed discrete and continuous models. The tutorial is in two parts. In the first part, I introduce an extension of the algebraic
decision diagram (ADD) to continuous variables - termed the extended ADD (XADD) - to represent arbitrary piecewise functions over
discrete and continuous variables and show how to efficiently compute elementary arithmetic operations, integrals, and
maximization for these functions. In the second part, I cover a wide range of novel applications where the XADD may be applied:
(a) exact inference in expressive discrete and continuous variable graphical models, (b) factored, parameterized linear and
quadratic optimization, and (c) exact solutions to continuous state and action Markov decision processes - which includes
closed-form exact solutions to previously unsolved problems in operations research. The tutorial is accompanied by free software
that audience members may wish to download in order to gain hands-on experience with examples from the tutorial.
Slides:
Software:
Topic Coverage:
- Parts 1 and 2: Discrete and Continuous Inference with Decision Diagrams
- Discrete and Continuous Case Calculus
- Basic representation of discrete and continuous functions
- Addition, subtraction, multiplication, and division
- Binary maximization and minimization
- Discrete summation
- Continuous integration (integral over x)
- Continuous maximization (max/min out x)
- Decision Diagram Types
- Binary and Algebraic
- Continuous Extensions
- Edge-labeled (Affine) Extensions
- Algorithms (theory and practice)
- Reduction
- Apply: Binary Operator Application
- Other operations
- Part 3: Applications
- Graphical Model Inference
- Probabilistic Query Computation
- Expectation Computation
- Bayesian Inference
- Sequential Decision Making
- Continuous State and Discrete Action MDPs
- Continuous State and Continuous Action MDPs
- Continuous State, Continuous Observation and Discrete Action POMDPs
- Constrained Optimization
- Optimization via Dynamic Programming
- Parameterized Optimization