Message Passing Algorithms for Hierarchical Dynamical Models

Abstract

Building models to understand patterns is one of the fundamental pursuits of science. Among such models, dynamical models are ubiquitous in most scientific fields as these models describe how processes evolve. These models can be found in finance, navigation, control engineering, audio signal processing, and telecommunications. Applications range from tracking the position of an aircraft to estimating the variance of returns on assets. Inference corresponds to computing posterior distributions over the variables of a given model. This dissertation describes a theoretical framework for deriving customized message passing-based inference algorithms in factor graphs and illustrates the framework’s application to hierarchical dynamical models. Factor graphs are visual representations of the dependency structures among the variables of a model. Inference tasks on a given model can be realized using message passing algorithms on the corresponding factor graph, where propagated messages are computed by integration (summation). Often, dynamical models of natural processes are constructed hierarchically. Because the hierarchies in the models may grow the complexity of dependence structures, exact inference by message passing in these models becomes infeasible and computationally impossible in a real-time setting. To employ hierarchical dynamical models in applications that require real-time processing, inference by message passing needs to be approximated. This dissertation proposes a constraint manipulation strategy to derive message passing algorithms on Forney-style factor graphs that pave the way for an efficient implementation of automated approximate inference. By changing the constraints on the local sub-graphs, we derive various local message update rules as the stationary solutions of a constrained Bethe free energy from first principles. By combining these local updates, one can perform hybrid message passing. Constraint manipulation is a modular way of generating message-passing algorithms by combining local updates such that factorized computations of local updates allow efficient implementation.

İsmail Şenöz

Chief Scientist
LazyDynamics

Ismail Senoz is a co-founder & chief scientist of Lazy Dynamics