Marginalization in models generated by compositional expressions. (English) Zbl 1363.05246

The paper is a contribution to the theory of compositional models, an alternative to Bayesian networks for the representation and processing of multidimensional probability distributions. The approach is based on the so called operator of composition that constructs from two low-dimensional distributions a distribution of a higher dimension. When comparing with Bayesian networks, the advantage of these models is that one can do with probability theory, one do not use graphs to represent a distribution structure.
The paper is a continuation of the author’s paper [Kybernetika 50, No. 3, 322–362 (2014; Zbl 1366.62103); erratum ibid. 51, No. 2, 387–388 (2015; Zbl 1340.05198)]. The present paper extends the previous one especially in the way that it does not restrict its consideration to expressions in which each element appears only once, and thus it reflects the requirements of applications more realistically. Moreover, the author studies general models in which the building blocks (low-dimensional distributions) are assembled (composed) in an arbitrary order predetermined by parentheses.
The author proposes several computational procedures for marginalizing general compositional expressions and studies their computational complexity. He focuses on two basic marginalization problems, which he calls single-marginal and marginal-representation problems. When solving the former problem he is interested in finding the simplest (from the computational point of view) procedure computing a given marginal distribution. As the name suggests, the goal of the later problem is to find a suitable structure making efficient computations of arbitrary marginal distributions possible.
The author considers in the paper not only probability distributions with values from interval \([0,1]\), but distributions whose values form an arbitrary semifield. This generalization enables him to apply the described apparatus, for example, to multidimensional databases, in which query answering requires to combine data stored in distinct tables.


05C90 Applications of graph theory
05C65 Hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
65C50 Other computational problems in probability (MSC2010)
60E99 Distribution theory
68T37 Reasoning under uncertainty in the context of artificial intelligence
Full Text: DOI Link


[1] Aho, A. V., Hopcroft, J. E., Ullman, J. D.: Data Structures and Algorithms. Addison-Wesley Pub. Co, Reading 1987. · Zbl 0487.68005
[2] Aji, S. M., McEliece, R.-J.: The generalized distributive law. IEEE Trans. Inform. Theory 46 (2000), 325-343. · Zbl 0998.65146 · doi:10.1109/18.825794
[3] Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. J. ACM 30 (1983), 479-513. · Zbl 0624.68087 · doi:10.1145/2402.322389
[4] Bína, V., Jiroušek, R.: Marginalization in multidimensional compositional models. Kybernetika 42 (2006), 405-422. · Zbl 1249.65010
[5] Gaubert, S., Plus, Max: Methods and applications of (max, +) linear algebra. Proc. XIV Symp. on Theoretical Aspects of Computer Science Hansestatdt Luebeck 1997. · doi:10.1007/bfb0023465
[6] Jiroušek, R.: Composition of probability measures on finite spaces. Proc. XIII International Conf. on Uncertainty in Artificial Intelligence (D. Geiger and P. P. Shenoy, Morgan Kaufmann, San Francisco 1997, pp. 274-281.
[7] Jiroušek, R.: Marginalization in composed probabilistic models. Proc. XVI International Conf. on Uncertainty in Artificial Intelligence, (C. Boutilier and M. Goldszmidt, Morgan-Kauffmann Pub., San Francisco 2000, vol. C, pp. 301-308. · doi:10.1016/b978-1-4832-1451-1.50041-x
[8] Jiroušek, R.: Decomposition of multidimensional distributions represented by perfect sequences. Ann. Math. Artif. Intelligence 5 (2002), 215-226. · Zbl 1004.60010 · doi:10.1023/A:1014591402750
[9] Jiroušek, R.: Foundations of compositional model theory. Int. J. General Systems 40 (2011), 623-678. · Zbl 1252.68285 · doi:10.1080/03081079.2011.562627
[10] Jiroušek, R.: Local computations in Dempster-Shafer theory of evidence. Int. J. Approx. Reasoning 53 (2012), 1155-1167. · Zbl 1266.68177 · doi:10.1016/j.ijar.2012.06.012
[11] Jiroušek, R.: On causal compositional models: simple examples. Proc. XIV International Conference on Information Processing and Management of Uncertainty in Knowledge-Bases Systems (IPMU 2014) (A. Laurent et al., Part I, CCIS 442, pp. 517-526. · doi:10.1007/978-3-319-08795-5_53
[12] Jiroušek, R., Kratochvíl, V.: Marginalization algorithm for compositional models. Proc. XI International Conference on Information Processing and Management of Uncertainty in Knowledge-Bases Systems (IPMU 2006) (B. Bouchon-Meunier and R.R. Yager, pp. 2300-2307.
[13] Jiroušek, R., Kratochvíl, V.: Foundations of compositional models: structural properties. Int. J. General Systems 44 (2015), 2-25. · Zbl 1330.93007 · doi:10.1080/03081079.2014.934370
[14] Jiroušek, R., Shenoy, P. P.: Compositional models in valuation-based systems. Int. J. Approx. Reasoning 55 (2014), 277-293. · Zbl 1252.68310 · doi:10.1007/978-3-642-31724-8_70
[15] Jiroušek, R., Vejnarová, J.: General framework for multidimensional models. Int. J. General Systems 18 (2003), 107-127. · Zbl 1029.68131 · doi:10.1002/int.10077
[16] Jiroušek, R., Vejnarová, J., Daniels, M.: Composition models of belief functions. Proc. V Symp. on Imprecise Probabilities and Their Applications (G. De Cooman, J. Vejnarová and M. Zaffalon, Action M Agency, Prague 2007, pp. 243-252.
[17] Kohlas, J.: Information algebras: generic structures for inference. Springer-Verlag, 2003. · Zbl 1027.68060 · doi:10.1007/978-1-4471-0009-6
[18] Kohlas, J., Pouly, M., Schneuwly, C.: Generic local computation. J. Comput. System Sciences 78 (2012), 348-369. · Zbl 1255.68156 · doi:10.1016/j.jcss.2011.05.012
[19] Kohlas, J., Schmid, J.: An algebraic theory of information: an introduction and survey. Information 5 (2014), 219-254. · doi:10.3390/info5020219
[20] Kohlas, J., Shenoy, P. P.: Computation in valuation algebras. Handbook of Defeasible Reasoning and Uncertainty Management Systems, Volume 5: Algorithms for Uncertainty and Defeasible Reasoning (J. Kohlas and S. Moral, Kluwer, Dordrecht 2000, pp. 5-39. · Zbl 1015.68196 · doi:10.1007/978-94-017-1737-3_2
[21] Kohlas, J., Wilson, N.: Semiring induced valuation algebra: exact and approximate local computation algorithms. Artificial Intelligence 172 (2008), 1360-1399. · Zbl 1183.68287 · doi:10.1016/j.artint.2008.03.003
[22] Kratochvíl, V.: Probabilistic compositional models: solution of an equivalence problem. Int. J. Approx. Reasoning 54 (2013), 590-601. · Zbl 1316.68181 · doi:10.1016/j.ijar.2013.01.002
[23] Kschinschang, F. R., Frey, B. J., Loeliger, H.-A.: Factor graphs and the sum-product algorithm. IEEE Trans. Inform. Theory 47 (2001), 498-519. · Zbl 0998.68234 · doi:10.1109/18.910572
[24] Lauritzen, S. L.: Graphical Models. Oxford University Press, Oxford 1996. <a href=”http://dx.doi.org/10.1002/(sici)1097-0258(19991115)18:213.0.co;2-a” target=”_blank”>DOI 10.1002/(sici)1097-0258(19991115)18:213.0.co;2-a |
[25] Litvinov, G. L., (eds.), S. N. Sergeev: 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] Malvestuto, F. M.: 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] Malvestuto, F. M.: Equivalence of compositional expressions and independence relations in compositional models. Kybernetika 50 (2014), 322-362. · Zbl 1366.62103 · doi:10.14736/kyb-2014-3-0322
[28] Malvestuto, F. M.: Erratum: Equivalence of compositional expressions and independence relations in compositional models. Kybernetika 51 (2015), 387-388. · Zbl 1340.05198 · doi:10.14736/kyb-2015-2-0387
[29] Speyer, D., Sturmfels, B.: Tropical mathematics. Mathematics Magazine 82 (2009), 163-173. · Zbl 1227.14051 · doi:10.4169/193009809X468760
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.