AAAI 2016 Tutorial: Symbolic Methods for Hybrid Inference, Optimization, and Decision-making

Speaker:

• Scott Sanner (Oregon State University; ssanner [at] gmail.com )

Abstract:

To date, our ability to perform exact closed-form inference or optimization in hybrid domains (that is, containing mixed discrete and continuous variables) is largely limited to special well-behaved cases. This tutorial argues that with an appropriate representation and data structure, we can vastly expand the class of models for which we can perform exact, closed-form inference.

In this tutorial, I review the algebraic decision diagram (ADD) and introduce an extension 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. Then I cover a wide range of novel applications where the XADD may be applied: (1) exact learning and inference in expressive discrete and continuous variable graphical models, (2) factored, parameterized linear and quadratic optimization, and (3) exact solutions to continuous state, action, and observation MDPs and POMDPs.

Slides:

• Part 1: Discrete
• Parts 2,3: Continuous, Applications

Software:

• AADDs: DD-Inference Source Repository
• XADDs: XADD-Inference Source Repository

Topic Coverage:

• 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
• 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