Kybernetika 52 no. 5, 696-723, 2016

Compositional models, Bayesian models and recursive factorization models

Francesco M. MalvestutoDOI: 10.14736/kyb-2016-5-0696

Abstract:

Compositional models are used to construct probability distributions from lower-order probability distributions. On the other hand, Bayesian models are used to represent probability distributions that factorize according to acyclic digraphs. We introduce a class of models, called \emph{recursive factorization models}, to represent probability distributions that recursively factorize according to sequences of sets of variables, and prove that they have the same representation power as both compositional models generated by sequential expressions and Bayesian models. Moreover, we present a linear (graphical) algorithm for deciding if a conditional independence is valid in a given recursive factorization model.

Keywords:

conditional independence, compositional model, Bayesian model, Markov property, recursive model, sequential expression

Classification:

05C65, 05C85, 1699, 65C50, 60E99, 68T37

paper.pdf

References:

  1. A. V. Aho, J. E. Hopcroft and J. D. Ullman: Data Structures and Algorithms. Addison-Wesley Pub. Co, Reading 1987.   CrossRef
  2. V. Bína and R. Jiroušek: On computations with causal compositional models. Kybernetika 51 (2015), 525-539.   DOI:10.14736/kyb-2015-3-0525
  3. D. Geiger, T. Verma and J. Pearl: Identifying independence in Bayesian networks. Networks 20 (1990), 507-534.   DOI:10.1002/net.3230200504
  4. R. Jiroušek: Composition of probability measures on finite spaces. In: Proc. XIII International Conference on Uncertainty in Artificial Intelligence (D. Geiger and P. P. Shenoy, eds.), Morgan Kaufmann, San Francisco 1997, pp. 274-281.   DOI:10.1023/a:1014591402750
  5. R. Jiroušek: Decomposition of multidimensional distributions represented by perfect sequences. Ann. Math. Artif. Intelligence 5 (2002), 215-226.   DOI:10.1023/a:1014591402750
  6. R. Jiroušek: Foundations of compositional model theory. Int. J. General Systems 40 (2011), 623-678.   CrossRef
  7. R. Jiroušek: Local computations in Dempster-Shafer theory of evidence. Int. J. Approx. Reasoning 53 (2012), 1155-1167.   DOI:10.1016/j.ijar.2012.06.012
  8. R. Jiroušek: On causal compositional models: simple examples. In: Proc. XIV International Conference on Information Processing and Management of Uncertainty in Knowledge-Bases Systems (IPMU 2014) (A. Laurent et al., eds.), Part I, CCIS 442, pp. 517-526.   DOI:10.1007/978-3-319-08795-5_53
  9. R. Jiroušek and V. Kratochvíl: Foundations of compositional models: structural properties. Int. J. General Systems 44 (2015), 2-25.   DOI:10.1080/03081079.2014.934370
  10. R. Jiroušek and P. P. Shenoy: Compositional models in valuation-based systems. Int. J. Approx. Reasoning 55 (2014), 277-293.   DOI:10.1016/j.ijar.2013.02.002
  11. R. Jiroušek and J. Vejnarová: General framework for multidimensional models. Int. J. Approx. Reasoning 18 (2003), 107-127.   DOI:10.1002/int.10077
  12. R. Jiroušek, J. Vejnarová and M. Daniels: Composition models of belief functions. In: Proc. V Symp. on Imprecise Probabilities and Their Applications (G. De Cooman, J. Vejnarová and M. Zaffalon, eds.), Action M Agency, Prague 2007, pp. 243-252.   CrossRef
  13. V. Kratochvíl: Characteristic properties of equivalent structures in compositional models. Int. J. of Approx. Reasoning 52 (2011), 599-612.   DOI:10.1016/j.ijar.2010.12.005
  14. V. Kratochvíl: Probabilistic compositional models: solutions of an equivalence problem. Int. J. Approx. Reasoning 54 (2013), 590-601.   DOI:10.1016/j.ijar.2013.01.002
  15. S. L. Lauritzen: Graphical Models. Oxford University Press, Oxford 1996.   CrossRef
  16. S. L. Lauritzen, A. P. Dawid, B. N. Larsen and H.-G. Leimer: Independence properties of directed Markov fields. Networks 20 (1990), 491-505.   DOI:10.1002/net.3230200503
  17. D. Maier: The Theory of Relational Databases. Computer Science Press, 1983.   CrossRef
  18. F. M. Malvestuto: A join-like operator to combine data cubes, and answer queries from multiple data cubes. ACM Trans. Database Systems 39, (2014), 3, 1-31.   DOI:10.1145/2638545
  19. F. M. Malvestuto: Equivalence of compositional expressions and independence relations in compositional models. Kybernetika 50 (2014), 322-362.   DOI:10.14736/kyb-2014-3-0322
  20. F. M. Malvestuto: Marginalization in models generated by compositional expressions. Kybernetika 51 (2015), 541-570.   DOI:10.14736/kyb-2015-4-0541
  21. F. M. Malvestuto: A general composition operator for probabilistic compositional models. Unpublished manuscript (2016).   CrossRef
  22. J. Pearl: Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann Pub., San Mateo 1988.   CrossRef
  23. E. Pourabbas and A. Shoshani: Efficient estimation of joint queries from multiple OLAP databases. ACM Trans. Database Systems 32 (2007), 1, Article No. 2.   DOI:10.1145/1206049.1206051
  24. R. E. Tarjan and M. Yannakakis: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13 (1984), 566-579.   DOI:10.1137/0213035
  25. T. Verma and J. Pearl: Causal networks: semantics and expressiveness. In: Proc. IV Workshop on Uncertainty in Artificial Intelligence, St. Paul 1988, pp. 352-359.   CrossRef