## 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
1. Discrete and Continuous Case Calculus
1. Basic representation of discrete and continuous functions
2. Addition, subtraction, multiplication, and division
3. Binary maximization and minimization
4. Discrete summation
5. Continuous integration (integral over x)
6. Continuous maximization (max/min out x)
2. Decision Diagram Types
1. Binary and Algebraic
2. Continuous Extensions
3. Edge-labeled (Affine) Extensions
3. Algorithms (theory and practice)
1. Reduction
2. Apply: Binary Operator Application
3. Other operations
• Part 3: Applications
1. Graphical Model Inference
1. Probabilistic Query Computation
2. Expectation Computation
3. Bayesian Inference
2. Sequential Decision Making
1. Continuous State and Discrete Action MDPs
2. Continuous State and Continuous Action MDPs
3. Continuous State, Continuous Observation and Discrete Action POMDPs
3. Constrained Optimization
1. Optimization via Dynamic Programming
2. Parameterized Optimization