Structured Message Passing
  In this paper, we present structured message passing (SMP), a unifying
framework for approximate inference algorithms that take advantage of
structured representations such as algebraic decision diagrams and sparse hash
tables. These representations can yield significant time and space savings over
the conventional tabular representation when the message has several identical
values (context-specific independence) or zeros (determinism) or both in its
range. Therefore, in order to fully exploit the power of structured
representations, we propose to artificially introduce context-specific
independence and determinism in the messages. This yields a new class of
powerful approximate inference algorithms which includes popular algorithms
such as cluster-graph Belief propagation (BP), expectation propagation and
particle BP as special cases. We show that our new algorithms introduce several
interesting bias-variance trade-offs. We evaluate these trade-offs empirically
and demonstrate that our new algorithms are more accurate and scalable than
state-of-the-art techniques.
