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 = {Melibari, Mazen and Poupart, Pascal and Doshi, Prashant and Trimponias, George}, booktitle = {Proceedings of the Eighth International Conference on Probabilistic Graphical Models}, pages = {345--355}, year = {2016}, editor = {Antonucci, Alessandro and Corani, Giorgio and Campos}, Cassio Polpo}, 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 = {https://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 %P 345--355 %U https://proceedings.mlr.press/v52/melibari16.html %V 52 %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 DA - 2016/08/15 ED - Alessandro Antonucci ED - Giorgio Corani ED - Cassio Polpo Campos} ID - pmlr-v52-melibari16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 52 SP - 345 EP - 355 L1 - http://proceedings.mlr.press/v52/melibari16.pdf UR - https://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 Proceedings of Machine Learning Research 52:345-355 Available from https://proceedings.mlr.press/v52/melibari16.html.

Related Material