Kybernetika 51 no. 4, 541-570, 2015

Marginalization in models generated by compositional expressions

Francesco M. MalvestutoDOI: 10.14736/kyb-2015-4-0541

Abstract:

In the framework of models generated by compositional expressions, we solve two topical marginalization problems (namely, the \emph{single-marginal problem} and the \emph{marginal-representation problem}) that were solved only for the special class of the so-called ``canonical expressions". We also show that the two problems can be solved ``from scratch" with preliminary symbolic computation.

Keywords:

marginalization, compositional expression, compositional model, syntax tree

Classification:

05C65, 05C85, 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. S. M. Aji and R.-J. McEliece: The generalized distributive law. IEEE Trans. Inform. Theory 46 (2000), 325-343.   DOI:10.1109/18.825794
  3. C. Beeri, R. Fagin, D. Maier and M. Yannakakis: On the desirability of acyclic database schemes. J. ACM 30 (1983), 479-513.   DOI:10.1145/2402.322389
  4. V. Bína and R. Jiroušek: Marginalization in multidimensional compositional models. Kybernetika 42 (2006), 405-422.   CrossRef
  5. S. Gaubert and Max Plus: Methods and applications of (max, +) linear algebra. In: Proc. XIV Symp. on Theoretical Aspects of Computer Science Hansestatdt Luebeck 1997.   DOI:10.1007/bfb0023465
  6. R. Jiroušek: Composition of probability measures on finite spaces. In: Proc. XIII International Conf. on Uncertainty in Artificial Intelligence (D. Geiger and P. P. Shenoy, eds.), Morgan Kaufmann, San Francisco 1997, pp. 274-281.   CrossRef
  7. R. Jiroušek: Marginalization in composed probabilistic models. In: Proc. XVI International Conf. on Uncertainty in Artificial Intelligence, (C. Boutilier and M. Goldszmidt, eds.), Morgan-Kauffmann Pub., San Francisco 2000, vol. C, pp. 301-308.   DOI:10.1016/b978-1-4832-1451-1.50041-x
  8. R. Jiroušek: Decomposition of multidimensional distributions represented by perfect sequences. Ann. Math. Artif. Intelligence 5 (2002), 215-226.   DOI:10.1023/a:1014591402750
  9. R. Jiroušek: Foundations of compositional model theory. Int. J. General Systems 40 (2011), 623-678.   DOI:10.1080/03081079.2011.562627
  10. 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
  11. 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
  12. R. Jiroušek and V. Kratochvíl: Marginalization algorithm for compositional models. In: Proc. XI International Conference on Information Processing and Management of Uncertainty in Knowledge-Bases Systems (IPMU 2006) (B. Bouchon-Meunier and R.R. Yager, eds.), pp. 2300-2307.   CrossRef
  13. 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
  14. 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
  15. R. Jiroušek and J. Vejnarová: General framework for multidimensional models. Int. J. General Systems 18 (2003), 107-127.   DOI:10.1002/int.10077
  16. 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
  17. J. Kohlas: Information algebras: generic structures for inference. Springer-Verlag, 2003.   DOI:10.1007/978-1-4471-0009-6
  18. J. Kohlas, M. Pouly and C. Schneuwly: Generic local computation. J. Comput. System Sciences 78 (2012), 348-369.   DOI:10.1016/j.jcss.2011.05.012
  19. J. Kohlas and J. Schmid: An algebraic theory of information: an introduction and survey. Information 5 (2014), 219-254.   DOI:10.3390/info5020219
  20. J. Kohlas and P. P. Shenoy: Computation in valuation algebras. In: Handbook of Defeasible Reasoning and Uncertainty Management Systems, Volume 5: Algorithms for Uncertainty and Defeasible Reasoning (J. Kohlas and S. Moral, eds.), Kluwer, Dordrecht 2000, pp. 5-39.   DOI:10.1007/978-94-017-1737-3_2
  21. J. Kohlas and N. Wilson: Semiring induced valuation algebra: exact and approximate local computation algorithms. Artificial Intelligence 172 (2008), 1360-1399.   DOI:10.1016/j.artint.2008.03.003
  22. V. Kratochvíl: Probabilistic compositional models: solution of an equivalence problem. Int. J. Approx. Reasoning 54 (2013), 590-601.   DOI:10.1016/j.ijar.2013.01.002
  23. F. R. Kschinschang, B. J. Frey and H.-A. Loeliger: Factor graphs and the sum-product algorithm. IEEE Trans. Inform. Theory 47 (2001), 498-519.   DOI:10.1109/18.910572
  24. S. L. Lauritzen: Graphical Models. Oxford University Press, Oxford 1996.   DOI:10.1002/(sici)1097-0258(19991115)18:21<2983::aid-sim198>3.0.co;2-a
  25. G. L. Litvinov and S. N. Sergeev (eds.): Proc. of the International Workshop TROPICAL-07 on Tropical and Idempotent Mathematics. Contemporary Mathematics 495 (2007), American Mathematical Society.   DOI:10.1090/conm/616
  26. F. M. Malvestuto: A join-like operator to combine data cubes, and answer queries from multiple data cubes. ACM Trans. Database Syst. 39 (2014), 3, 1-31.   DOI:10.1145/2638545
  27. 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
  28. F. M. Malvestuto: Erratum: Equivalence of compositional expressions and independence relations in compositional models. Kybernetika 51 (2015), 387-388.   DOI:10.14736/kyb-2015-2-0387
  29. D. Speyer and B. Sturmfels: Tropical mathematics. Mathematics Magazine 82 (2009), 163-173.   DOI:10.4169/193009809x468760