Marginalization in models generated by compositional expressions

Malvestuto, Francesco M.

Kybernetika, Tome 51 (2015) no. 4, pp. 541-570

Abstract (VO)

In the framework of models generated by compositional expressions, we solve two topical marginalization problems (namely, the single-marginal problem and the 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.

Détail

DOI : 10.14736/kyb-2015-4-0541

Classification : 05C65, 05C85, 60E99, 65C50, 68T37
Keywords: compositional expression; compositional model; marginalization; syntax tree

Bibliographie

[1] Aho, A. V., Hopcroft, J. E., Ullman, J. D.: Data Structures and Algorithms. Addison-Wesley Pub. Co, Reading 1987. | MR | Zbl

[2] Aji, S. M., McEliece, R.-J.: The generalized distributive law. IEEE Trans. Inform. Theory 46 (2000), 325-343. | DOI | MR | Zbl

[3] Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. J. ACM 30 (1983), 479-513. | DOI | MR | Zbl

[4] Bína, V., Jiroušek, R.: Marginalization in multidimensional compositional models. Kybernetika 42 (2006), 405-422. | MR | Zbl

[5] Gaubert, S., Plus, Max: Methods and applications of (max, +) linear algebra. In: Proc. XIV Symp. on Theoretical Aspects of Computer Science Hansestatdt Luebeck 1997. | DOI

[6] Jiroušek, R.: 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.

[7] Jiroušek, R.: 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

[8] Jiroušek, R.: Decomposition of multidimensional distributions represented by perfect sequences. Ann. Math. Artif. Intelligence 5 (2002), 215-226. | DOI | MR | Zbl

[9] Jiroušek, R.: Foundations of compositional model theory. Int. J. General Systems 40 (2011), 623-678. | DOI | MR | Zbl

[10] Jiroušek, R.: Local computations in Dempster-Shafer theory of evidence. Int. J. Approx. Reasoning 53 (2012), 1155-1167. | DOI | MR | Zbl

[11] Jiroušek, R.: 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

[12] Jiroušek, R., Kratochvíl, V.: 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.

[13] Jiroušek, R., Kratochvíl, V.: Foundations of compositional models: structural properties. Int. J. General Systems 44 (2015), 2-25. | DOI | MR

[14] Jiroušek, R., Shenoy, P. P.: Compositional models in valuation-based systems. Int. J. Approx. Reasoning 55 (2014), 277-293. | DOI | MR | Zbl

[15] Jiroušek, R., Vejnarová, J.: General framework for multidimensional models. Int. J. General Systems 18 (2003), 107-127. | DOI | Zbl

[16] Jiroušek, R., Vejnarová, J., Daniels, M.: 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.

[17] Kohlas, J.: Information algebras: generic structures for inference. Springer-Verlag, 2003. | DOI | Zbl

[18] Kohlas, J., Pouly, M., Schneuwly, C.: Generic local computation. J. Comput. System Sciences 78 (2012), 348-369. | DOI | MR | Zbl

[19] Kohlas, J., Schmid, J.: An algebraic theory of information: an introduction and survey. Information 5 (2014), 219-254. | DOI

[20] Kohlas, J., Shenoy, P. P.: 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 | MR | Zbl

[21] Kohlas, J., Wilson, N.: Semiring induced valuation algebra: exact and approximate local computation algorithms. Artificial Intelligence 172 (2008), 1360-1399. | DOI | MR

[22] Kratochvíl, V.: Probabilistic compositional models: solution of an equivalence problem. Int. J. Approx. Reasoning 54 (2013), 590-601. | DOI | MR

[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. | DOI | MR

[24] Lauritzen, S. L.: Graphical Models. Oxford University Press, Oxford 1996. | DOI | MR

[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 | MR

[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 | MR

[27] Malvestuto, F. M.: Equivalence of compositional expressions and independence relations in compositional models. Kybernetika 50 (2014), 322-362. | DOI | MR

[28] Malvestuto, F. M.: Erratum: Equivalence of compositional expressions and independence relations in compositional models. Kybernetika 51 (2015), 387-388. | DOI | MR

[29] Speyer, D., Sturmfels, B.: Tropical mathematics. Mathematics Magazine 82 (2009), 163-173. | DOI | MR | Zbl