Dynamic Sum Product Networks for Tractable Inference on Sequence Data

Mazen Melibari, Pascal Poupart, Prashant Doshi, George Trimponias
; Proceedings of the Eighth International Conference on Probabilistic Graphical Models, PMLR 52:345-355, 2016.

Abstract

Sum-Product Networks (SPN) have recently emerged as a new class of tractable probabilistic 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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v52-melibari16, title = {Dynamic Sum Product Networks for Tractable Inference on Sequence Data}, author = {Mazen Melibari and Pascal Poupart and Prashant Doshi and George Trimponias}, booktitle = {Proceedings of the Eighth International Conference on Probabilistic Graphical Models}, pages = {345--355}, year = {2016}, editor = {Alessandro Antonucci and Giorgio Corani and Cassio Polpo Campos}}, volume = {52}, series = {Proceedings of Machine Learning Research}, address = {Lugano, Switzerland}, month = {06--09 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v52/melibari16.pdf}, url = {http://proceedings.mlr.press/v52/melibari16.html}, abstract = {Sum-Product Networks (SPN) have recently emerged as a new class of tractable probabilistic 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.} }
Endnote
%0 Conference Paper %T Dynamic Sum Product Networks for Tractable Inference on Sequence Data %A Mazen Melibari %A Pascal Poupart %A Prashant Doshi %A George Trimponias %B Proceedings of the Eighth International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2016 %E Alessandro Antonucci %E Giorgio Corani %E Cassio Polpo Campos} %F pmlr-v52-melibari16 %I PMLR %J Proceedings of Machine Learning Research %P 345--355 %U http://proceedings.mlr.press %V 52 %W PMLR %X Sum-Product Networks (SPN) have recently emerged as a new class of tractable probabilistic 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.
RIS
TY - CPAPER TI - Dynamic Sum Product Networks for Tractable Inference on Sequence Data AU - Mazen Melibari AU - Pascal Poupart AU - Prashant Doshi AU - George Trimponias BT - Proceedings of the Eighth International Conference on Probabilistic Graphical Models PY - 2016/08/15 DA - 2016/08/15 ED - Alessandro Antonucci ED - Giorgio Corani ED - Cassio Polpo Campos} ID - pmlr-v52-melibari16 PB - PMLR SP - 345 DP - PMLR EP - 355 L1 - http://proceedings.mlr.press/v52/melibari16.pdf UR - http://proceedings.mlr.press/v52/melibari16.html AB - Sum-Product Networks (SPN) have recently emerged as a new class of tractable probabilistic 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. ER -
APA
Melibari, M., Poupart, P., Doshi, P. & Trimponias, G.. (2016). Dynamic Sum Product Networks for Tractable Inference on Sequence Data. Proceedings of the Eighth International Conference on Probabilistic Graphical Models, in PMLR 52:345-355

Related Material