  Sum-Product Networks (SPN) have recently emerged as a new class of tractable
probabilistic graphical models. Unlike Bayesian networks and Markov networks
where inference may be exponential in the size of the network, inference in
SPNs is in time linear in the size of the network. Since SPNs represent
distributions over a fixed set of variables only, we propose dynamic sum
product networks (DSPNs) as a generalization of SPNs for sequence data of
varying length. A DSPN consists of a template network that is repeated as many
times as needed to model data sequences of any length. We present a local
search technique to learn the structure of the template network. In contrast to
dynamic Bayesian networks for which inference is generally exponential in the
number of variables per time slice, DSPNs inherit the linear inference
complexity of SPNs. We demonstrate the advantages of DSPNs over DBNs and other
models on several datasets of sequence data.
