Dynamic Sum Product Networks for Tractable Inference on Sequence Data (Extended Version)
This work addresses the need for efficient probabilistic modeling of sequences in domains like time-series analysis, offering a tractable alternative to exponential-time methods.
The paper tackles the problem of modeling sequence data of varying length with tractable inference by proposing dynamic sum product networks (DSPNs), which generalize sum-product networks (SPNs) using a template network repeated as needed, and demonstrates advantages over dynamic Bayesian networks (DBNs) and other models on several datasets.
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.