[Colloquium] Sanner talk - Thursday 8/12, 2pm at TTI

[Meridel Trimble]

TOYOTA TECHNOLOGICAL INSTITUTE TALK

Speaker: Scott Sanner (University of Toronto)

Title: Affine Algebraic Decision Diagrams (AADDs) and their Application to
Structured Probabilistic Inference

Time: Thursday, August 12, 2pm
Place: TTI-C (1427 E. 60th St., 2nd Floor)
REFRESHMENTS PROVIDED

Speaker's Homepage: http://www.cs.toronto.edu/~ssanner/

Abstract:
Algebraic Decision Diagrams (ADDs) provide an efficient means for
representing functions that map from a propositional domain to a numeric
(or algebraic) range.  They do so by exploiting logical structure in order
to avoid fully enumerating the propositional domain.  Due to the
compactness of ADDs and the existence of efficient algorithms for
performing arithmetic operations on them, ADDs have proven useful for a
variety of probabilistic inference problems ranging from inference in
Bayesian networks to solving for optimal value functions in factored
Markov decision processes (MDPs).  However, ADDs cannot efficiently
represent additive or multiplicative structure and thus tend to be
inefficient when applied to problems exhibiting such structure.

To resolve this deficiency, we introduce an affine extension to ADDs that
allows them to compactly represent logical, additive, and multiplicative
structure - all within a single canonical representation.  We introduce
the algorithms and caching mechanisms required to maintain and efficiently
compute with these AADDs.  And in analogy to ADDs, we demonstrate a
general approximation scheme that allows one to obtain minimum and maximum
bounds on an AADD function representation, when either time or space
prevent an exact computation.  We apply AADDs to the same domains where
ADDs have been previously applied (MDPs and Bayesian Networks), showing
that they never perform worse than ADDs (validating a fundamental
theoretic result), and in certain cases perform exponentially better.

This is joint work with David McAllester.

If you have questions, or would like to meet the speaker, please contact
Meridel at 4-9873 or mtrimble at tti-c.org